04.二维数组的查找 (Easy)*

题目描述*

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:*

现有矩阵 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。

给定 target = 20，返回 false。

限制*

0 <= n <= 1000, 0 <= m <= 1000

代码*

从右上角或左下角开始，根据 target 与元素值的大小关系移动。不能从左上角或右下角，不然不知道往哪移动了。复杂度 O(m + n)

第二次做这个题感觉这个方法太慢了，感觉应该可以用二分做的。开始是对行列分别二分，但显然不对，以示例为例，以行首元素判断二分，最后得到 5 是在 3 和 10 之间，可见这样并不对，因为并不是下一行的元素一定大于上一行所有元素。看到题解里说可以从对角线遍历，每次从对角线元素开始从两个方向进行二分查找。

简单遍历二分查找

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0 || matrix[0].size() == 0) {
            return false;
        }
        int i = 0, j = matrix[0].size() - 1;
        while(i < matrix.size() && j >= 0) {
            if(target == matrix[i][j]) {
                return true;
            }else if(target > matrix[i][j]) {
                i++;
            }else {
                j--;
            }
        }
        return false;
    }
};

class Solution {
    bool binary_search(vector<vector<int>>& matrix, int target, int i, bool isVertical) {
        int l = i, r = (isVertical ? matrix.size() - 1 : matrix[0].size() - 1);
        if(isVertical) {
            while(l <= r) {
                int mid = l + (r - l) / 2;
                if(target == matrix[mid][i]) {
                    return true;
                }else if(target > matrix[mid][i]) {
                    l = mid + 1;
                }else {
                    r = mid - 1;
                }
            }
        }else {
            while(l <= r) {
                int mid = l + (r - l) / 2;
                if(target == matrix[i][mid]) {
                    return true;
                }else if(target > matrix[i][mid]) {
                    l = mid + 1;
                }else {
                    r = mid - 1;
                }
            }
        }
        return false;
    }
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        if(n == 0) {
            return false;
        }
        int m = matrix[0].size();
        if(m == 0) {
            return false;
        }
        for(int i = 0; i < m && i < n; i++) {
            if(binary_search(matrix, target, i, true) || binary_search(matrix, target, i, false)) {
                return true;
            }
        }
        return false;
    }
};

最后更新: July 23, 2022