【刷题笔记】二维数组中的查找

题目：

在一个 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof

解答：

        针对此题，当然最好想的自然就是暴力去遍历每一个元素，依次进行比较。但是这样一来实际复杂度为n^2不说，而且题目中给的依次递增条件是一点也没有利用起来啊。

        那么我们就顺着从左到右依次递增，从上到下依次递增的思路去看：

        就上面的例子来说，如果我们从第一个（下标为0 0）开始找的话，找5，那么第一次就有两个选择，要么走右，要么走下，如果可以同时走两条路的话，那么到后面去就会出现问题的，所以直接从第一个进行找不行。

        既然我们是从第一个去找的，是不是也就是说我们只需要找到一个标志的位置，能够一条路走完，不会出现两个选择就好了吗？没错，根据特性，从左到右递增，从上到下递增。最底下的那一行就是其所在列的最大数，最左边的那一列的数就是其所在行的最小数。那么这样的话，一旦出现数比其大，就只能在此行往右边走，比其小，只能在此列往上走。--这样每次的选择就有一个，就不会存在问题了。这也便就是最后一行第一列的数开始找。

代码如下：

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