LeetCode74——Search a 2D Matrix-蒲公英云

LeetCode74——Search a 2D Matrix

二维数组查找问题，二重循环暴力搜索肯定是超时的，好在二维数组有一定的规律：

1.每一行从左到右是非递减的

2.每一列从上到下是非递减的

那么根据这个条件我们很容易得出：

1.给定一个数 number 如果他比矩阵中的某个数nums[i][j]大，则存在两种情况：

这个数要么在nums[i][j]的右侧，要么在nums[i][j]的下侧。

2.给定一个数 number 如果他比矩阵中的某个数nums[i][j]小，也存在两种情况：

这个数要么在nums[i][j]的左侧，要么在nums[i][j]的上侧。

如何根据上述规律进行查找？

由于不论是比较结果是大还是小，都存在两种情况，这样判断起来就会产生疑惑：

当出现大或者小的情况下，我们究竟该往哪个方向继续比较？

对于这样一个二维矩阵，我们考虑从它的右上角或者左下角为起点进行迭代：

右上角为起点（nums[0][len-1]）

那么比较起来比target小的数一定在左边，比target的大的数一定在下面。

左下角为起点（nums[len-1][0]）

那么比较起来比target小的数一定在上面，比target的大的数一定在右边。

上述两种情况任意选一种写出代码都能通过。

代码：

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