题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
数据范围
二维数组中元素个数范围 [0,1000]
样例
输入数组： [ [1,2,8,9]， [2,4,9,12]， [4,7,10,13]， [6,8,11,15] ] 如果输入查找数值为7，则返回true， 如果输入查找数值为5，则返回false。
方法一：单调性扫描 O(n)
本题要利用子矩阵右上角的单调性质，因为右上角的值要大于它的左边，小于它的下边。
由此，可以得到如下思路：
如果 x 等于 target ，则找到了目标值，返回 true 即可。
如果 x 大于 target ，则说明目标值在 x 的左边，故 j-- 。
如果 x 小于 target ，则说明目标值在 x 的右边，故 i++ 。
如果遍历到头了还没有找到，则返回 false 即可。
class Solution { public: bool searchArray(vector<vector<int>> array, int target) { if (array.empty() || array[0].empty()) return false; int i = 0, j = array[0].size() - 1; //从矩阵的右上角开始扫描 while (i < array.size() && j >= 0) { int t = array[i][j]; if (t == target) return true; if (t > target) j--; else i++; } return false; } };
欢迎大家在评论区交流~
