LeetCode 240. 搜索二维矩阵 II（C++）_240. 搜索二维矩阵 iic++

1.题目如下：

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true
1
2

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false
1
2

提示：

m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10^ 9<= matrix[i][j] <= 10^9
每行的所有元素从左到右升序排列 每列的所有元素从上到下升序排列
-10^ 9 <= target <= 10^9

2.代码如下 ：

class Solution {
public:
/**思路一：直接遍历查找；时间复杂度O(nm),超出限制*/
/*
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[0].size();j++){
                if(target==matrix[i][j]){
                    return true;
                }
            }
        }
        return false;
    }
*/

/**思路二：由于每一行都是升序，所以每一行都可以用可用二分查找；时间复杂度O(mlogn)*/
/*
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(int i=0;i<matrix.size();i++){
            if(binarySearch(matrix[i],target,0,matrix[0].size()-1)){
                return true;
            }
        }
        return false;
    }

    bool binarySearch(vector<int>& nums,int target,int left,int right){
        if(left>right){
            return false;
        }
        if(left==right){
            if(nums[left]==target){
                return true;
            }
            return false;
        }
        int mid=(left+right)/2;
        if(nums[mid]>target){
            return binarySearch(nums,target,left,mid);
        }
        else if (nums[mid]==target){
            return true;
        }
        else{
            return binarySearch(nums,target,mid+1,right);
        }

    }
    */
/**思路三：Z字查找：从右上角[0][n-1]开始查找，如果>target向左一列；如果<target向下一行*/

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int i=0;
        int j=matrix[0].size()-1;
        while(i<matrix.size() && j>=0){
            if(matrix[i][j]>target){
                j--;
            }
            else if (matrix[i][j]==target){
                return true;
            }
            else{
                i++;
            }
        }
        return false;
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70