【LeetCode-74】搜索二维矩阵

10.5 搜索二维矩阵【74】

10.5.1 题目描述

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

每行中的整数从左到右按升序排列。
每行的第一个整数大于前一行的最后一个整数。

10.5.2 方法一：两次二分查找

思路

由于每行的第一个元素大于前一行的最后一个元素，且每行元素是升序的，所以每行的第一个元素大于前一行的第一个元素，因此矩阵第一列的元素是升序的。

我们可以对矩阵的第一列的元素二分查找，找到最后一个不大于目标值的元素，然后在该元素所在行中二分查找目标值是否存在。

代码

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowIndex = binarySearchFirstColumn(matrix, target);
        if (rowIndex < 0) {
            return false;
        }
        return binarySearchRow(matrix[rowIndex], target);
    }

    public int binarySearchFirstColumn(int[][] matrix, int target) {
        int low = -1, high = matrix.length - 1;
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (matrix[mid][0] <= target) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    public boolean binarySearchRow(int[] row, int target) {
        int low = 0, high = row.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
}
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

复杂度分析

• 时间复杂度：$O(\log m+\log n)=O(\log mn)$，其中 m 和 n 分别是矩阵的行数和列数。
• 空间复杂度：O(1)。

10.5.3 方法二：一次二分查找

思路

若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素。

代码实现时，可以二分升序数组的下标，将其映射到原矩阵的行和列上。

代码

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

复杂度分析

• 时间复杂度：O(logmn)，其中 m 和 n 分别是矩阵的行数和列数。
• 空间复杂度：O(1)。

结语
两种方法殊途同归，都利用了二分查找，在二维矩阵上寻找目标值。值得注意的是，若二维数组中的一维数组的元素个数不一，方法二将会失效，而方法一则能正确处理。

10.5.4 my answer—二分查找

class Solution {
    public static boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left_x = 0,left_y = 0,right_x = m - 1,right_y = n - 1;
        while(left_x < right_x || (left_x == right_x && left_y <= right_y)){
            int dis  = (right_x*n + right_y + 1)-(left_x*n + left_y + 1);   // 求左右两点坐标之间的差
            int mid_x = left_x + (dis/2)/n;     // 求左右两坐标的中点坐标的横坐标
            int mid_y = -1;
            if((left_y + (dis/2)%n)<n){         // 求左右两坐标的中点坐标的众坐标
                mid_y = left_y + (dis/2)%n;
            }else{
                mid_x++;
                mid_y = (left_y + (dis/2)%n)%n;
            }
            if(matrix[mid_x][mid_y]>target){
                if(mid_y==0){
                    right_x = mid_x-1;
                    right_y = n-1;
                }else{
                    right_x = mid_x;
                    right_y = mid_y-1;
                }
            }else if(matrix[mid_x][mid_y]<target){
                if(mid_y==n-1){
                    left_x = mid_x + 1;
                    left_y = 0;
                }else{
                    left_x = mid_x;
                    left_y = mid_y + 1;
                }
            }else{
                return true;
            }
        }
        return false;

    }
}
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