题目
给定一个有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; } } }
}
|
近期评论