题目描述

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

解答1

首先想到的是通过暴力算法来求解该问题。但实际思考过程中，明显感觉到暴力求解的双重循环有很大部分的重复工作。

暴力求解通过第一层循环遍历每一行，然后第二层循环对每一行的元素从左到右进行遍历，并与target进行比较。如果相等，则返回true；如果该行的所有元素都比target小或者中途碰到一个比target大的元素，就可以转入到对下一行的遍历了。

可以发现，上面的暴力求解其实只用到了输入矩阵每一行元素单调递增这一个特性。考虑到矩阵还有一个特性是，它的每一列元素也是递增的。
--> 针对这一点，可以对暴力求解算法进行一点点优化。
从上往下遍历每一行时，如果发现第i行中的第j列元素值大于target，那么后续在遍历i+1行时，就无需再遍历该行中第j列及其之后列的元素，因为它们肯定是要比target大的。

代码实现：在暴力求解算法的基础上加入对第二层循环的遍历列数的裁剪操作。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int rows = array.size();
        if(!rows) return false;
        int cols = array[0].size();

        for(int i=0; i<rows; i++)
        {
            for(int j = 0; j<cols; j++)
            {
                if(array[i][j] == target)
                {
                    return true;
                }
                else if(array[i][j] > target) // 进行裁剪操作
                {
                    cols = j; // 下一次只需要从0遍历到第j-1列即可
                    break;
                }
            }
        }
        return false;
    }
};

解答2

在自己想到了上面的解题思路之后，再去看了看评论中对该题的解答。发现有一种很巧妙的思路，只需要O(行数+列数)的时间复杂度。（上面解法1的时间复杂度应该有O(行数*log(列数))）。
该解题思路充分利用了矩阵行和列的单调特性。从左下角（或右上角，效果是一样的）开始，往上移（行数减一），则值减小，往右移（列数加一），则值增加。

• 若当前元素等于target，则return true
• 若当前元素小于target，则说明符合要求的元素在当前元素的右侧，执行列数++；
• 若当前元素大于target，则说明符合要求的元素在当前元素的上侧，执行行数--；

（注意循环的退出条件：当前元素所在行<0或当前元素所在列>=array的列数）

以下是以左下角作为起点的完整C++代码：

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int rows = array.size();
        if(rows==0) return false;
        int cols = array[0].size();

        int curX = rows-1, curY = 0;
        while(curX>=0 && curY<cols)
        {
            if(array[curX][curY] == target)
            {
                return true;
            }
            else if(array[curX][curY] > target)
            {
                curX--;
            }
            else
            {
                curY++;    
            }
        }
        return false;
    }
};