4. 二维数组中的查找
1. 描述
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
2. 例子
示例 1:
现有矩阵 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。
3. 限制
- 0 <= n <= 1000
- 0 <= m <= 1000
4. 题解
m = i_matrix.size(), n = i_matrix.front().size()
时间复杂度: O(m + n)
空间复杂度: O(1)
利用右上角或左下角特殊点进行快速筛选。以右上角为例，其同列下方的值都更大，而同行左边的值都更小，因此我们每次可以用目标值与其进行对比，并每次快速排除一行或一列。
class Solution
{
public:
// bool findNumberIn2DArray(vector<vector<int>>& matrix, int target)
bool findNumberIn2DArray(vector<vector<int>> &i_matrix, int target)
{
if(i_matrix.empty() || i_matrix.front().empty()) return false;
const int rows = i_matrix.size();
const int colums = i_matrix.front().size();
for(int i = 0, j = colums - 1; i < rows && j >= 0; )
{
if(i_matrix[i][j] == target) return true;
target > i_matrix[i][j] ? i++ : j--;
}
return false;
}
};