题解 | #二维数组中的查找#

题目主要信息:

• 题目给定了一个二维数组，即二维矩阵，每一行元素从左到右是递增，每一列元素从上到下是递增
• 需要我们判断这个矩阵中是否出现了给定数字target

具体思路:

传统的思维可能就是从上到下遍历矩阵每一行，对于每一行再从左到右遍历每个元素，然后查看target是否出现在了矩阵中，这种方法可行，但是浪费了题目给的矩阵是在一定程度上是有序的这个条件。既然矩阵每一行从左到右递增，每一列从上到下递增，那么左上角的元素一定最小，右下角的元素一定最大。我们假定遇到了矩阵中某个元素，如果它比目标值target大，那么目标值应该在它的上面或者左边，如果它比目标值target小，那么目标值应该在它的下面或者右边。那我们可以找一个位置开始，每当元素比目标值大它就往右走，每当元素比目标值小，它就往上走，很明显左下角这个位置就很合适。

• step 1：优先判断矩阵行列为0的特殊情况。
• step 2：从矩阵左下角开始，如果目标值比较大，它一定在右方，如果目标值比较小它一定在上方。
• step 3：直到遍历到矩阵另外的边界也没找到就意味着不存在。

查找过程可以参考如下图示：

代码实现:

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.size() == 0)  //优先判断特殊
            return false;
        int n = array.size();
        if(array[0].size() == 0) 
            return false;
        int m = array[0].size();
        for(int i = n - 1, j = 0; i >= 0 && j < m; ){ //从最左下角的元素开始往右或往上
            if(array[i][j] > target)   //元素较大，往上走
                i--;
            else if(array[i][j] < target) //元素较小，往右走
                j++;
            else
                return true;
        }
        return false;
    }
};

复杂度分析：

• 时间复杂度：$O(n+m)O(n+m)$，其中$nn$和$mm$分别是二维数组的两个边长，最坏情况查找经过一行一列
• 空间复杂度：$O(1)O(1)$，没有使用额外空间