Leetcode 74.搜索二维矩阵

,

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

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

示例

输入：matrix = [
[1, 3, 5, 7],
[10,11,16,20],
[23,30,34,60]
], target = 16
输出：true

思路

有序，查找类任务，想到二分查找

  1. 利用每一列，每一行有序的特性，先对第一列进行查找，再对那一行进行查找,时间复杂度为 O(lg mn)
    解法1

    先查找第一列，找到第二行，再查找第二行

  2. 利用有序的条件，从左下角开始查找，时间复杂度为O(m + n)
  • 当当前元素大于 target时, 向上查找
  • 当当前元素小于 target时, 向右查找
    解法2

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target)
    {
        auto p = upper_bound(matrix.begin(), matrix.end(),target, []( const int a, const vector<int>& b){
            return a < b[0];
        });
        if(p != matrix.begin()) { 
            -- p;
            return binary_search(p->begin(), p->end(),target);
        }
        return false; // 默认找不到
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &matrix, int target)
    {
        int m = matrix.size();
        int n = matrix[0].size();
        for (int i = m - 1, j = 0; i >= 0 &&j < n;)
        {
            if (matrix[i][j] < target)
                ++j;
            else if (matrix[i][j] > target)
                --i;
            else 
                return true;
        }
        return false; // 默认找不到
    }
};