排序矩阵查找(系列)

240. 搜索二维矩阵 II

给定M×N矩阵，每一行、每一列都按升序排列，请编写代码找出某元素。

---

看到这题，最简单的就是直接一次遍历所有元素，时间复杂度是O(m*n)。
当然，看到升序，也比较容易想到二分查找，可以按行遍历m次，每次使用二分查找。

但是，还有没有其他更好的办法呢？

倒三角线遍历

观察发现，如果从右上角开始遍历，直到左下角结束，假设当前元素为cur，可以发现：

1. 如果cur<target, 由于cur是这一行中最大的数，则可以舍弃这一行，cur下移
2. 如果cur>target, 由于cur是这一列中最小的数，则可以舍弃这一列，cur左移

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        if n == 0:
            return False
        
        column = n-1
        row = 0
        while row < m and column >= 0:
            if matrix[row][column] == target:
                return True
            elif matrix[row][column] < target:
                row += 1
            else:
                column = column - 1
        return False           

C++版本

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size();
        if (rows == 0) {
            return false;
        }
        int columns = matrix[0].size();
        int row = 0, column = columns - 1;
        while (row < rows && column >= 0) {
            int tmp = matrix[row][column];
            if (tmp == target) {
                return true;
            }else if (tmp > target) {
                column--;
            }else{
                row++;
            }
        }
        return false;
    }
};

当然, 从左下角走到右上角也是OK的, 代码如下：

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        if n == 0:
            return False
        
        row = m-1
        column = 0
        while row >=0 and column < n:
            if matrix[row][column] == target:
                return True
            elif matrix[row][column] < target:
                column += 1
            else:
                row = row - 1
        return False           

正三角遍历

将矩阵划分为四块：左上、右上、左下、右下，每次可以排除其中一块

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        def helper(matrix, x1, y1, x2, y2, x_max, y_max, target):
            # 越界
            if x1 > x_max or y1 > y_max:
                return False

            # 如果只有一个元素了
            if x1 == x2 and y1 == y2:
                return matrix[x1][y1] == target
            
            mid_x = x1 + (x2-x1)//2
            mid_y = y1 + (y2-y1)//2
            if matrix[mid_x][mid_y] == target:
                return True
            elif matrix[mid_x][mid_y] < target:
                right_up_result = helper(matrix, x1, mid_y+1, mid_x, y2, x2, y2,target) 
                left_down_result = helper(matrix, mid_x+1, y1, x2, mid_y, x2, y2,target)
                right_down_result = helper(matrix, mid_x+1, mid_y+1, x2, y2, x2, y2,target)
                return right_up_result or left_down_result or right_down_result
            else:
                right_up_result = helper(matrix, x1, mid_y+1, mid_x, y2, x2, y2,target) 
                left_down_result = helper(matrix, mid_x+1, y1, x2, mid_y, x2, y2,target)
                left_up_result = helper(matrix, x1, y1, mid_x, mid_y, x2, y2,target)
                return right_up_result or left_down_result or left_up_result
        m = len(matrix)
        if m == 0:
            return False
        n = len(matrix[0])
        if n == 0:
            return False
        
        return helper(matrix, 0, 0, m-1, n-1, m-1, n-1, target)

74. 搜索二维矩阵

编写一个高效的算法来判断m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

两次二分查找

可以先按第一列二分查找确定所在的行，然后再对行做一次二分

一次二分

将整个矩形视作一个一维数组，直接一次二分完成

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        
        m = len(matrix)
        n = len(matrix[0])
        total = m * n
        left = 0
        right = total-1
        # 考虑二者相等的情况
        while left <= right:
            mid = left + (right-left)//2
            x = matrix[mid//n][mid%n]
            # print("left, right, mid, m, n, x", left, right, mid, m, n, x)
            if x == target:
                return True
            elif x < target:
                left = mid + 1
            else:
                right = mid - 1
        # print('left, right', left, right)
        return False

C++版本

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size();
        if (rows == 0) {
            return false;
        }
        int columns = matrix[0].size();
        int left = 0, right = rows*columns-1;
        while (left <= right) {
            int mid = left + ((right-left) >> 1);
            int tmp = matrix[mid/columns][mid%columns];
            if (tmp == target) {
                return true;
            }else if(tmp < target) {
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return false;
    }
};