写出一个高效的算法来搜索 m * n
矩阵中的值,返回这个值出现的次数。
这个矩阵具有以下特性:
考虑下列矩阵:
[
[1, 3, 5, 7],
[2, 4, 7, 8],
[3, 5, 9, 10]
]
给出 target = 3
,返回 2
首先根据该矩阵的特性可得以下的规律:
所以根据此规律可得搜索思路:
从右上角搜索思路类似,只是方向不同。
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) {
if (matrix == null || matrix.length == 0) {
return 0;
}
int count = 0;
int n = matrix.length;
int m = matrix[0].length;
int x = n - 1;
while (x >= 0 && y < m) {
if (matrix[x][y] > target) {
x--;
} else if (matrix[x][y] < target) {
y++;
} else {
x--;
y++;
count++;
}
}
return count;
}
}