今天在lintCode上做了一道题，非常的简单，但是解题的思路太巧妙了，觉得有必要记录下来！
1.概览
(1).题意
写出一个高效的算法来搜索m×n矩阵中的值，返回这个值出现的次数。
这个矩阵具有以下特性：
每行中的整数从左到右是排序的。
每一列的整数从上到下是排序的。
在每一行或每一列中没有重复的整数。
(2).样例
考虑下列矩阵：
[
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]
]
给出target = 3，返回 2
(3).挑战
要求O(m+n) 时间复杂度和O(1) 额外空间
2.解题思路
这个题也是非常的简单！
首先，我们从数组的左下角开始遍历。如果当前的数字大于target，我们向上移，因为上面的小于下面的；如果当前的数字小于target，我们向右移，因为右边的大于左边的；如果当前的数字等于target的话，sum++,并且向右上移，因为右上角的数字有可能还等于target。
3.代码
public int searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0 || matrix[0][0] > target) {
return 0;
}
int sum = 0;
int x = 0;
int y = matrix.length - 1;
while(x < matrix[0].length && y >= 0) {
if(matrix[y][x] == target) {
sum++;
x++;
y--;
}else if(matrix[y][x] > target) {
y--;
}else {
x++;
}
}
return sum;
}
