Xing's Techlog

二维数组中的查找

Posted on Edited on In

在二维数组中查找。

相关题目：剑指Offer面试题4：二维数组中的查找Leetcode 74. Search a 2D Matrix, Leetcode 240. Search a 2D Matrix II。

问题1: 数组中的元素有什么特征？

问题2: 异常情况怎样处理？如matrix == null，matrix.length == 0, matrix[0].length == 0?

一般有两种情况，第一种情况：数组中的元素每行从左到右递增（递减），每列从上到下递增（递减），这时候我们可以用算法1。

算法1: 从非最小最大元素开始搜索

第一种矩阵如下所示：

1
2
3
4
1	2	8	9
2	4	9	12
4	7	10	13
6	8	11	15

这种情况下我们需要从右上角或者左下角开始搜索，每一次判断可以排除一行或者一列。

1
2
3
4
5
6
7
8
9
10
11
public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
    int row = 0;
    int col = (matrix[0].length - 1);
    while (row <= (matrix.length - 1) && col >= 0) {
        if (matrix[row][col] == target) return true;
        else if (matrix[row][col] < target) row++;
        else col--;
    }
    return false;
}

时间复杂度：O(n), Leetcode 15ms.

空间复杂度：O(1)

Leetcode 240. Search a 2D Matrix II 就可以用该解法。

第二种情况是：在第一中情况的条件下，新加一个条件：每行最后一个元素要大于下一行第一个元素。显然这种情况下我们还可以使用O(n)时间的算法1，但是我们可以根据新加的条件使用另一种速度更快的算法。

算法2: 二分查找

第二种矩阵如下所示：

1
2
3
1	3	5	7
10	11	16	20
23	30	34	50

由于矩阵在内存中是按顺序存储的，所以我们可以把整个矩阵当成一个有序数组，在数组上进行二分查找，这就涉及到一个问题：矩阵下标和数组下标的映射：

1
2
3
4
5
int m = matrix.length;
int n = matrix[0].length;

matrix[x][y] => array[x * n + y]
array[x]     => matrix[x / n][x % n]

有了上面的映射规则，我们可以得到如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
    int m = matrix.length;
    int n = matrix[0].length;
    int start = 0;
    int end = m * n - 1;
    int mid, num;
    while (start <= end) {
        mid = (start + end) >> 1;
        num = matrix[mid/n][mid%n];
        if (num == target) return true;
        else if (num > target) end = mid - 1;
        else start = mid + 1;
    }
    return false;
}

Leetcode 74. Search a 2D Matrix 就可以用这种解法。

时间复杂度：O(log(n*m))，Leetcode: 11ms

空间复杂度：O(1)

Related Posts