搜索二维矩阵Ⅱ

题意

写出一个高效的算法来搜索 m * n 矩阵中的值,返回这个值出现的次数。

这个矩阵具有以下特性:

  • 每行中的整数从左到右是排序的。
  • 每一列的整数从上到下是排序的。
  • 在每一行或每一列中没有重复的整数。

样例

考虑下列矩阵:

[

    [1, 3, 5, 7],

    [2, 4, 7, 8],

    [3, 5, 9, 10]

]

给出 target = 3,返回 2

思路

首先根据该矩阵的特性可得以下的规律:

  • 左下角的右侧均比其右侧的数字大
  • 左下角的下侧均比其左侧的数字大

所以根据此规律可得搜索思路:

  1. 从左下角开始搜索
  2. 如果此数比目标数大,则向上移动一位
  3. 如果此数比目标数小,则向右移动一位
  4. 如果此数等于目标数,则向上移动一位,再向右移动一位。
  5. 直至到最右侧或者最上侧为止。

从右上角搜索思路类似,只是方向不同。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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;
}
}

原题地址

LintCode:搜索二维矩阵Ⅱ

坚持原创技术分享,您的支持将鼓励我继续创作!