leetcode--74. 搜尋二維矩陣

1. 搜尋二維矩陣

   編寫一個高效的算法來判斷 m x n 矩陣中，是否存在一個目标值。該矩陣具有如下特性：

每行中的整數從左到右按升序排列。

每行的第一個整數大于前一行的最後一個整數。

示例 1:

輸入:

matrix = [

[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]

]

target = 3

輸出: true

示例 2:

輸入:

matrix = [

[1, 3, 5, 7],

[10, 11, 16, 20],

[23, 30, 34, 50]

]

target = 13

輸出: false

思路一：二分法

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if (m == 0){
            return false;
        }
        int n = matrix[0].size();
        int left = 0, right = m * n - 1;
        int x = 0, y = 0, mid = 0;
        while (left <= right){
            mid = (left + right) / 2
            x = mid / n;
            y = mid % n;
            if (matrix[x][y] == target){
                return true;
            } else if (matrix[x][y] < target){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
};
/*12ms,13.4MB*/
           

時間複雜度：O(log(nm))

空間複雜度：O(1)

思路二：左下角标志法

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        if (m == 0){
            return false;
        }
        int n = matrix[0].size();
        if (n == 0){
            return false;
        }
        int x = m - 1, y = 0;
        while (x >= 0 && y < n){
            if (matrix[x][y] == target){
                return true;
            } else if (matrix[x][y] > target){
                x--;
            } else {
                y++;
            }
        }
        return false;
    }
};
/*8ms,13.4MB*/
           

時間複雜度：O(n+m)

空間複雜度：O(1)