Kevin's Blog
0%

剑指offer T3：二维数组中的查找

发表于 更新于

二维数组（m*n）中的查找：

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

input: [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]]
input: 5

output: true

方法一：遍历法 (略)

1
2
3
4
5
6
7
...
    for i 
        for j
            ...
        end
    end
...

方法2：对对角元素上进行筛选（略）

使得A(i,i) <= target <= A(i+1,i+1)，则只需要对数组的左下角和右上角进行遍历即可，还可以进行递归操作优化。最坏的情况比方法1减少至少一半操作量，不过还是要遍历。

方法3：通过四个边界进行筛选

四条边界线，四种情况讨论：(在下面的循环中如果有相等的元素则直接return true)

  • 上边界：如果matrix[0][i] < target < matrix[0][i+1]，则第i+1列及之后的可以筛选出去
  • 下边界：如果matrix[m-1][j] < target < matrix[m-1][j+1]，则第j列及之前的可以筛选出去
  • 左边界：如果matrix[h][0] < target < matrix[h+1][0]，则第h+1行及之后可以筛选出去
  • 右边界：如果matrix[k][n-1] < target < matrix[k+1][n-1]，则第k行及之前可以筛选出去
matrix[0][i]
matrix[k+1][n-1]
matrix[h][0]
matrix[m-1][j+1]

k+1<=h and j+1<=i一定成立

所以需要遍历k+1 -> h行，j+1 -> i列，matrix[k+1][j+1] -> matrix[h][i]

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
public boolean findNumberIn2DArray(int[][] matrix, int target) {
     if((matrix==null||matrix.length==0)||(matrix.length==1&&matrix[0].length==0)) {
        return false;
     }
    int m = matrix.length, n = matrix[0].length;
    int hl=m-1,kr=0,it=n-1,jbo=0;

    for (int posl = 0; posl < m; posl++) { //posl 是左边界 left
        if (matrix[posl][0] == target) return true;
        if (posl+1 < m && matrix[posl][0] < target && matrix[posl + 1][0] > target) {
            hl = posl;
            break;
        }
    } 

    for (int posr = 0; posr < m; posr++) { //posr 是右边界 right
        if (matrix[posr][n-1] == target) return true;
        if (posr+1 < m && matrix[posr][n-1] < target && matrix[posr + 1][n-1] > target) {
            kr = posr + 1;
            break;
        }
    }

    for (int post = 0; post < n; post++) { //post 是上边界 top
        if (matrix[0][post] == target) return true;
        if (post+1 < n && matrix[0][post] < target && matrix[0][post + 1] > target) {
            it = post;
            break;
        }
    } 

    for (int posb = 0; posb < n; posb++) { //posb 是下边界 bottom
        if (matrix[m-1][posb] == target) return true;
        if (posb+1 < n && matrix[m-1][posb] < target && matrix[m-1][posb + 1] > target) {
            jbo = posb+1;
            break;
        }
    }

     for (int i = kr;i <= hl; i++) {
        for (int j = jbo; j <= it; j++) {
            if (matrix[i][j] == target) {
                return true;
            }
        }
    }
    return false;
}

线性查找

从右上角开始查找，如何target小于matrix(i,j)的值，则往左一行查找，即matrix(i,j-1)

如果target 大于matrix(i,j)的值，往下一行查找，即matrix(i+1,j)

一直循环下去，如果满足直接return true，否则return false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int row = 0, column = columns - 1;
        while (row < rows && column >= 0) {
            int num = matrix[row][column];
            if (num == target) {
                return true;
            } else if (num > target) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }
}