题目描述
给定一个有N×M的整型矩阵matrix和一个整数K，matrix每行每列都排好序了。
实现一个函数，判断K是否在matrix中。
分析
- 从右上角的数开始寻找
- 右上角比k小，说明k不可能在第一行了，看下面的行
- 右上角比k大，说明k不可能在最后一列，看左边的列
代码实现
public class FindNumInSortMatrix {
public static int[] find(int[][] matrix, int num) {
// 1-----------------------------------------------------
int a = 0;// 行
int b = matrix[0].length - 1;// 列
while (a < matrix.length && b > -1) {
if (matrix[a][b] == num) {
return new int[] { a, b };
} else if (matrix[a][b] < num) { // 2-------------------------
a++;// 往下一行走
} else { // 3-----------------------------------------------------
b--;// 往该列左走
}
}
return new int[] { -1, -1 };
}
public static void main(String[] args) {
int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int num1 = 5;
int arr1[] = find(matrix, num1);
System.out.println(num1 + "在" + (arr1[0] + 1) +"行" + (arr1[1] + 1) + "列");
int num2 = 7;
int arr2[] = find(matrix, num2);
System.out.println(num2 + "在" + (arr2[0] + 1) +"行" + (arr2[1] + 1) + "列");
}
}
测试结果
