描述
写出一个高效的算法来搜索m×n矩阵中的值，返回这个值出现的次数。
这个矩阵具有以下特性：
每行中的整数从左到右是排序的。
每一列的整数从上到下是排序的。
在每一行或每一列中没有重复的整数。
样例
考虑下列矩阵：
[
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]
]
给出target = 3，返回 2
思路
本题并不是一道二分法的题，最优的时间复杂度与行列数有关，即O(m+n)；观察矩阵应该从左下角或右上角着手，这样用O(1)的时间就能排除一行一列
代码
public class Solution {
/**
* @param matrix: A list of lists of integers
* @param: A number you want to search in the matrix
* @return: An integer indicate the occurrence of target in the given matrix
*/
public int searchMatrix(int[][] matrix, int target) {
// check corner case
if (matrix == null || matrix.length == 0) {
return 0;
}
if (matrix[0] == null || matrix[0].length == 0) {
return 0;
}
// from bottom left to top right
int n = matrix.length; // 行
int m = matrix[0].length; // 列
int x = n - 1;
int y = 0;
int count = 0;
// 从左下角开始，矩阵没有重复元素
// while 每执行一次，只执行一句 if ，因为上面一句的 if 改变了 x y，下一句 if 如果不重新判断 x y 是否越界，可能会报错
while (x >= 0 && y < m) {
if (matrix[x][y] == target) {
x--;
y++;
count++;
} else (matrix[x][y] < target) {
y++;
} else {
x--;
}
}
return count;
}
}
