题目
在一个\(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
思路
一开始看有序数组，还以为可以二分，但实际上并不能。首先题目说了数组有以下下特点：
- 每一行的数右边最大
- 每一列的数上面最小
找一个数是否存在的套路大致是这样，找一个数看是不是目标，如果不是排除一些数，继续找下一个，直到所有的数排除，或者找到为止。
最简单的方法就是\(n*m\)的遍历，但这样显然没有利用增序关系。如何利用这个增序关系呢？一个具体的思路是选择一行最大的，如果比这个最大的还大，那么这一行就直接排除，比他小就比同行下一列。这样最坏就是\(n*m\)
同样的，那列是不是也可以一起比呢？如果从\((n, m)\)位置开始就不行，这个地方每一行每一列都是最大的，只有同时比这个数大才能排除。否则单独比行大，确比列小会导致目标可能存在左侧或者右侧，具体见书。这也就是书中所说的有重叠。但如果我们换个位置从\((0, m)\)或者\((n, 0)\)开始，就能解决这个问题。
时间复杂度\(O(n+m)\)
代码
#include<iostream>
#include<vector>
using namespace std;
class Solution {
public:
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0) return false;
int row = matrix.size(), column = matrix[0].size();
int now_row = 0, now_column = column-1;
while(now_row < row && now_column >= 0) {
int value = matrix[now_row][now_column];
if (target == value) return true;
else if (target > value) now_row++;
else now_column--;
}
return false;
}
};
int main() {
int a[][5] = {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};
vector<vector<int>> input;
for (int i = 0; i < 5; i++) {
vector<int> tmp;
for (int j = 0; j < 5; j++){
tmp.push_back(a[i][j]);
}
input.push_back(tmp);
}
Solution s;
cout << s.findNumberIn2DArray(input, 5) << endl;
}