https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
思路：做法太多了，最简单的暴力，复杂度
O
(
n
m
)
O(nm)
O
(
n
m
)
，或者依次考虑每行/每列，然后二分判断，复杂度
O
(
n
l
g
m
)
O(nlgm)
O
(
n
l
g
m
)
或者
O
(
m
l
g
n
)
O(mlgn)
O
(
m
l
g
n
)
。这里就说一下最巧妙的
O
(
n
+
m
)
O(n+m)
O
(
n
+
m
)
的做法，考虑以矩形右上角为起始点，那么我们可以比较
m
a
t
r
i
x
x
,
y
matrix_{x,y}
m
a
t
r
i
x
x
,
y
与
t
a
r
g
e
t
target
t
a
r
g
e
t
的大小关系：
-
前者大于后者，由于每一列从上至下是单调增的，因此这一列可以排除掉，令
y−
1
y-1
y
−
1
即可。 -
前者小于后者，由于每一行从左至右是单调增的，因此这一行可以排除掉，令
x+
1
x+1
x
+
1
即可。 - 前者等于后者，直接返回True。
当x、y越界时，说明没有找到解，那么返回False即可。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int n=matrix.size(),m=matrix[0].size();
int x=0,y=m-1;
while(x<n&&y>=0)
{
if(matrix[x][y]>target)
--y;
else if(matrix[x][y]<target)
++x;
else
return 1;
}
return 0;
}
};