LeetCode 74. 搜索二维矩阵_查找一个二维整数矩阵

74. 搜索二维矩阵

难度中等585收藏分享切换为英文接收动态反馈

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

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

示例 1：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
1
2

示例 2：

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
1
2

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

题解

二维二分

​ 这道题应该也是二分的改版，二维二分，先二分搜索出行坐标，然后在二分搜索出列坐标。直接上代码吧

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int row = rowSearch(matrix, target);//行坐标
        if(row != -1){//行坐标不为0
            return binSearch(matrix[row], target);
        }
        return false;
    }

    int rowSearch(int[][] matrix, int target){//搜索行坐标
        int start = 0;//开始行
        int end = matrix.length - 1;//结束行
        int mid = 0;
        while(start <= end){
            mid = start + ((end - start) / 2);//防止溢出
            if(mid + 1 < matrix.length){//防止越界
                if(target < matrix[mid][0]){//小于当场，尾指针前移
                    end = mid - 1;
                } else if(target >= matrix[mid][0] && target < matrix[mid + 1][0]){//在当前行，返回
                    return mid;
                } else {//大于当前行，头指针后移
                    start = mid + 1; 
                }
            } else {//mid+1越界，返回最后一行
                return mid;
            }
            
        }
        return -1;
    }

    boolean binSearch(int[] matrix, int target){//二分搜索
        int start = 0;
        int end = matrix.length - 1;
        int mid = 0;
        while(start <= end){
            mid = start + ((end - start) / 2);
            if(target == matrix[mid]){
                return true;
            } else if(target < matrix[mid]){
                end = mid - 1;
            } else {
                start = 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
38
39
40
41
42
43
44
45
46
47
48

官方题解：直接二分

​ 没看到的时候真想不起来，看到后才想起，其实我们的二维三维数组等等，在内存都是一维存储的，只要弄清楚关系就可以线性找到某个元素。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;//多少行
        int n = matrix[0].length;//多少列
        int start = 0;//头指针
        int end = m * n -1;//尾指针
        while(start <= end){
            int mid = (end - start) / 2 + start;
            int x = matrix[mid / n][mid % n];//[mid / n]表示映射第几行，[mid % n]表示行的第几列
            if(target == x){//target等于x，返回
                return true;
            } else if(target < x){//target小于x，尾指针前移
                end = mid - 1;
            } else {//target大于x，头指针后移
                start = mid + 1;
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20