思路:

  1. 初始化,从 (0, M-1) 位置上开始遍历
  2. 如果 K 小于 当前位置上的值,在当前 的左部分进行查找
  3. 如果 K 大于 当前位置上的值,在当前 的下部分进行查找
  4. 如果当前位置已经 越界,则返回 No,证明当前矩阵中没有该 K

解释:

  1. 因为 每行 的数据是 从小到大 排列的,所以,如果当前位置上的值 大于 K 值,那么肯定往 当前行 的左部分进行查找
  2. 因为 每列 的数据是 从小到大 排列的,所以,如果当前位置上的值 小于 K 值,那么肯定往 当前列 的下部分进行查找
  3. 按照上述的查找方式,最坏情况下 也就遍历了 NM 列,时间复杂度为 O(N+M)O(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;
    }
}