算法初级——有序矩阵查找

在行列都排好序的矩阵中找数
【题目】 给定一个有N*M的整型矩阵matrix和一个整数K,matrix的每一行和每一 列都是排好序的。实现一个函数,判断K是否在matrix中。 例如:
0 1 2 5
2 3 4 7
4 4 4 8
5 7 7 9
如果K为7,返回true;如果K为6,返回false。
【要求】 时间复杂度为O(N+M),额外空间复杂度为O(1)。
/*
* 在行列都排好序的矩阵中找数
* 【题目】 给定一个有N*M的整型矩阵matrix和一个整数K,matrix的每一行和每一 列都是排好序的。实现一个函数,判断K是否在matrix中。
* 例如: 0 1 2 5
* 2 3 4 7
* 4 4 4 8
* 5 7 7 9
* 如果K为7,返回true;如果K为6,返回false。
* 【要求】 时间复杂度为O(N+M),额外空间复杂度为O(1)。
*
* 从右上角开始,如果大于右上角,向下移动,如果小于,向左移动。
*/

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
public class 有序矩阵查找 {

    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 = 10;
    System.out.println(isContains(matrix, K));
    }

    private static boolean isContains(int[][] matrix, int k) {
        int r = 0;
        int c = matrix[0].length - 1;
        while(r < matrix.length && c >= 0) {
            if (matrix[r][c] == k) {
                return true;
            }else {
            if(k > matrix[r][c]) {
                r++;
            }else {
                c--;       
            }
        }
        }
        return false;      
    }
}
0 条评论
发表一条评论