在行列都排好序的矩阵中找数

发表于 阅读次数：

题目

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

思路

由于行和列都是排好序的，我们可以从矩阵的左下角或者右上角开始检查，有的兄弟萌可能就会问了为什么不能从左上角和右下角开始。我们先看下左上角和右下角的情况。

右上角是第一行中最大的值，也是该列中最小的值，
我们把当前的值叫做current，若K大于current,则current左边的所有值都可以排除掉，current的位置向下移动一位，若K小于current,则current下面的所有值都可以排除掉，current的位置也随之向左移动。直到找到K或者越界则方法结束。

左下角也是同理，这里就不作过多的赘述了

这时候我们再回头看一下左上角和右下角的情况，我们没有办法能够一次移动排除多种可能性，只能采用遍历的方式，所以我们选择左下角和右下角。

示例图

下面来看下实际代码。

实现

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
public static boolean isContains(int[][] matrix, int K) {

        int current = matrix[0][matrix[0].length - 1];
        int x = 0;
        int y = 0;
        while(x != matrix.length && y != -1){
            if(current == K) return true;

            if(current > K) {
                current = matrix[x][--y];
            }else {
                current = matrix[++x][y];
            }
        }

        return false;
    }

    public static void main(String[] args) {
        int[][] matrix = new int[][] { { 0, 1, 2, 3, 4, 5, 6 },// 0
                { 10, 12, 13, 15, 16, 17, 18 },// 1
                { 23, 24, 25, 26, 27, 28, 29 },// 2
                { 44, 45, 46, 47, 48, 49, 50 },// 3
                { 65, 66, 67, 68, 69, 70, 71 },// 4
                { 96, 97, 98, 99, 100, 111, 122 },// 5
                { 166, 176, 186, 187, 190, 195, 200 },// 6
                { 233, 243, 321, 341, 356, 370, 380 } // 7
        };
        int K = 233;
        System.out.println(isContains(matrix, K));
    }