思路:
- 初始化,从 (0, M-1) 位置上开始遍历
- 如果 K 小于 当前位置上的值,在当前 行 的左部分进行查找
- 如果 K 大于 当前位置上的值,在当前 列 的下部分进行查找
- 如果当前位置已经 越界,则返回 No,证明当前矩阵中没有该 K 值
解释:
- 因为 每行 的数据是 从小到大 排列的,所以,如果当前位置上的值 大于 K 值,那么肯定往 当前行 的左部分进行查找
- 因为 每列 的数据是 从小到大 排列的,所以,如果当前位置上的值 小于 K 值,那么肯定往 当前列 的下部分进行查找
- 按照上述的查找方式,最坏情况下 也就遍历了 N 行 M 列,时间复杂度为
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String[] NMK = scan.nextLine().split(" ");
int N = Integer.valueOf(NMK[0].trim());
int M = Integer.valueOf(NMK[1].trim());
int K = Integer.valueOf(NMK[2].trim());
int[][] matrix = new int[N][M];
for (int i = 0; i < N; i++) {
String[] numsStr = scan.nextLine().split(" ");
for (int j = 0; j < M; j++) {
matrix[i][j] = Integer.valueOf(numsStr[j]);
}
}
int cx = 0;
int cy = M - 1;
while (cx < N && cy > -1) {
if (matrix[cx][cy] < K) {
cx++;
} else if (matrix[cx][cy] > K) {
cy--;
} else {
System.out.println("Yes");
return;
}
}
System.out.println("No");
return;
}
}