题目
给定一个有N*M的整型矩阵matrix和一个整数K,matrix的每一行和每一列都是排好序的，例如下图矩阵：
要求：实现一个函数,判断K是否在matrix中。算法的时间复杂度为O(N+M)、额外空间复杂度为O(1)。
思路
- 创建一个指针，初始位置可选取排序矩阵中两个特殊的点，右上角的点和左下角的点
- 假设指针设置在了矩阵的右上角，在排好序的矩阵中，该点的特殊性为：大于左边的所有元素同时小于下方的所有元素
- 跟据该特性，判断指针所在位置的元素和整数k的关系：
- 等于k：返回true
- 大于k：指针向左移动，如果移动后超过了矩阵边界返回false
- 小于k：指针向下移动，如果移动后超过了矩阵边界返回false
- 重复执行上述步骤，直至函数return
代码
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
|
public class {
public static boolean isExist(int[][] matrix, int num) {
if (matrix == null) {
return false;
}
int[] index = {0, matrix[0].length - 1};
while (true) {
if (matrix[index[0]][index[1]] == num) {
return true;
} else if (matrix[index[0]][index[1]] > num) {
index[1]--;
} else {
index[0]++;
}
if (index[0] >= matrix.length || index[1] < 0) {
return false;
}
}
}
}
|
近期评论