题目来源：《程序员代码面试指南-IT名企算法与数据结构最优解》-左程云著

牛客网在线OJ系统地址：传送门

题目描述

给定一个N × M的整型矩阵matrix和一个整数K，matrix的每一行每一列都是排好序的。实现一个函数，判断K是否在matrix中。

要求：

时间复杂度为O(N + M)，额外空间复杂度为O(1)。

备注：

1 ⩽ N, M ⩽1000

0 ⩽ K, 矩阵中的数 ⩽ 10^9^

输入描述

第一行有三个整数N，M，K；

接下来N行，每行M个整数为输入的矩阵。

输出描述

若K存在于矩阵中输出"Yes"，否则输出"No"。

示例

示例一

输入：

1
2
3
2 4 5
1 2 3 4
2 4 5 6

输出：

1
Yes

示例二

输入：

1
2
3
2 4 233
1 2 3 4
2 4 5 6

输出：

1
No

思考

由于矩阵中的行和列都是排好序的，我们可以知道最后一列是每一行的最大值，最后一行是每一列的最大值。整个矩阵的最大值在右下角。

要想减少时间复杂度，我们必须能够快速排除某些行或列，基于最后一列或行是每一行或列的最大值的特点，我们可以从矩阵右上角或左下角开始查找，如果不是指定的数，我们就可以排除掉一行或一列了。

算法思路

思路一：从矩阵右上角开始查找

  1. 从矩阵最右上角的数开始查找（row=0,col=M-1：第0行，第M-1列）。
  2. 比较当前数matrix[row][col]与K的关系：
  • 如果等于K，则找到了，返回"Yes"，整个过程结束。
  • 如果大于K，则该列被排除，令col=col-1，重复步骤2。
  • 如果小于K，则该行被排除，令row=row+1，重复步骤2。
  1. 如果找到越界都没有找到与K相等的数，则返回"No"，整个过程结束。

思路二：从矩阵左下角开始查找

  1. 从矩阵最左上角的数开始查找（row=N-1,col=0：第N-1行，第0列）。
  2. 比较当前数matrix[row][col]与K的关系：
  • 如果等于K，则找到了，返回"Yes"，整个过程结束。
  • 如果大于K，则该行被排除，令row=row-1，重复步骤2。
  • 如果小于K，则该列被排除，令col=col+1，重复步骤2。
  1. 如果找到越界都没有找到与K相等的数，则返回"No"，整个过程结束。

代码实现（Java）

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // receive input params
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        // build matrix
        int[][] matrix = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }
        // do check
        boolean containsOne = isContainsOne(matrix, k);
        System.out.println(containsOne ? "Yes" : "No");
        
        // boolean containsTwo = isContainsTwo(matrix, k);
        // System.out.println(containsTwo ? "Yes" : "No");
    }

    /**
     * 判断方式一：双重for循环
     * 外层循环矩阵每一行
     * 内层循环矩阵每一列
     * 相等直接返回true；
     * 若小于k，则排除当前行，结束内层循环，遍历下一行。
     * 若大于k，则排除当前列，j--，内存循环进入下一次。
     * 若双重循环完成都未找到k，则返回false。
     * @param matrix
     * @param k
     * @return
     */
    private static boolean isContainsOne(int[][] matrix,int k) {
        int col = matrix[0].length;
        for (int[] ints : matrix) {
            for (int j = col - 1; j >= 0; j--) {
                int value = ints[j];
                if (value == k) {
                    return true;
                } else if (value < k) {
                    break;
                }
            }
        }
        return false;
    }

    /**
     * 判断方式二：while循环
     * 越界条件：行遍历完或列遍历完
     * @param matrix
     * @param k
     * @return
     */
    private static boolean isContainsTwo(int[][] matrix,int k) {
        int row = matrix.length;
        int col = matrix[0].length;
        int i = 0;
        int j = col - 1;
        while (i < row && j >= 0) {
            int value = matrix[i][j];
            if (value == k) {
                return true;
            } else if (value < k) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }
}