leetcode240 搜索二维矩阵 II

梦里梦外; 2021-12-23 07:27 234阅读 0赞

### 题目： ###

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。  
每列的元素从上到下升序排列。  
示例:

现有矩阵 matrix 如下：

> \[  
> \[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\]\]  
> 给定 target = 5，返回 true。  
> 给定 target = 20，返回 false。

--------------------

### 思路： ###

二分法。

1.  先获取当前矩阵的最大值和最小值，即左上角的值和右下角的值  
    为(x1,y1)和(x2,y2)。当x1 = x2 且 y1 = y2时，说明矩阵为一个点。
2.  求mid值，即 ( (x1+x2)/2 , (y1+y2)/2 )
3.  将mid值与target进行比较，来决定接下来取查询那些范围  
    · 如果target = mid 说明找到了目标值  
    · 如果target < mid，说明以mid为最小值的那块矩阵，不会有target， target在其他范围  
    · 如果target > mid，说明以mid为最大值的那块矩阵里，不会有target， target在其他范围里面
4.  接下来对其他范围进行递归查询

![1137338-20190320212242726-1166437883.png][]

### 代码： ###

class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length < 1 || matrix[0] == null || matrix[0].length < 1) {
                return false;
            }
            return searchMatrix(matrix,target,0,0,matrix.length-1,matrix[0].length-1);
        }
    
        //方法
        private boolean searchMatrix(int[][] matrix, int target, int x1, int y1, int x2, int y2) {
            if(x2 < x1 || y2 < y1){
                return false;
            }
            if(target < matrix[x1][y1] || target > matrix[x2][y2]){//若果小于矩阵最小值，或者大于矩阵最大值，直接返回false。
                return false;
            }
            int mid_x = (x1 + x2) / 2;
            int mid_y = (y1 + y2) / 2;
    
            if(target == matrix[mid_x][mid_y]){
                return true;
            }
            if(target < matrix[mid_x][mid_y]){ //target不在第四象限
                return (
                //查找第二象限
                searchMatrix(matrix,target,x1,y1,mid_x-1,mid_y-1) ||
                //查找第一象限
                searchMatrix(matrix,target,x1,mid_y,mid_x-1,y2) ||
                //查找第三象限
                searchMatrix(matrix,target,mid_x,y1,x2,mid_y-1)
                );
            }else { //target不在第二象限
                return (
                //查找第四象限
                searchMatrix(matrix, target,mid_x+1,mid_y+1,x2,y2) ||
                //查找第一象限
                searchMatrix(matrix,target,x1,mid_y+1,mid_x,y2) ||
                //查找第三象限
                searchMatrix(matrix,target,mid_x+1,y1,x2,mid_y)
                );
            }
        }
    }

但是我看其他人提交的代码，思路是从左下 或者 右上开始遍历。  
思路是：

> 从左下角角标开始查找  
> 如果>target 则向上移动角标  
> 如果<target 则向右移动角标  
> 如果==target 则返回True  
> 如果角标出界还没找到target 则返回False

### 但是我认为这种不是最优的，比如二维数组只有一行或者一列的话，这就是一次时间复杂度为O(n)的遍历。 ###

代码如下（代码是从右上角开始的）

class Solution {
        public boolean searchMatrix(int[][] matrix, int target){
            if (matrix.length==0)
                return false;
            int i = matrix.length-1,j=0;
            while(i>=0 && j<matrix[0].length){
                if (matrix[i][j] == target)
                    return true;
                else if(matrix[i][j]>target)
                    i--;
                else if(matrix[i][j]<target)
                    j++;
            }
            return false;
        }
    }

转载于:https://www.cnblogs.com/magicya/p/10562465.html

[1137338-20190320212242726-1166437883.png]: /images/20211223/9e83408f2ed6422e8be6e8ec721b679b.png