Cinte's Leetcode Record
0%

74. Search a 2D Matrix

Posted on Edited on In Disqus:
Symbols count in article: 1.2k Reading time ≈ 1 mins.

74. Search a 2D Matrix

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int i = m - 1, j = 0;
        while(i >= 0 && j < n)
        {
            if(matrix[i][j] < target)
                ++j;
            else if(matrix[i][j] > target)
                --i;
            else 
                return true;
        }
        return false;
    }
};

O(n)

对于这种方式，由于每行每列都是有序的，所以可以先通过二分查找第一列中最后一个不大于target的数，然后在那一行中二分搜索 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        auto row = upper_bound(matrix.begin(), matrix.end(), target, [](int a, vector<int>& v){
            return a < v[0];
        }); // 注意comp是value和容器中的元素比
        if(row == matrix.begin())
            return false;
        --row;
        return binary_search(row->begin(), row->end(), target);
    }
};
##### 二分搜索

虽然是个二维矩阵，但是每行排开来他就是个递增数列，但是这种方法没有很好的利用他矩阵的特点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int lo = 0, hi = m * n - 1;
        while(lo < hi)
        {
            int mid = lo + (hi - lo) / 2;
            if(matrix[mid / n][mid % n] >= target)
                hi = mid;
            else
                lo = mid + 1;
        }
        return matrix[hi / n][hi % n] == target;
    }
};

O(log(m * n))