题解 | #在行列都排好序的矩阵中找指定的数#

思路:

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

解释:

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