leetcode240 搜索二维矩阵 II

题目：

编写一个高效的算法来搜索 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。

思路：

二分法。

先获取当前矩阵的最大值和最小值，即左上角的值和右下角的值

为(x1,y1)和(x2,y2)。当x1 = x2 且 y1 = y2时，说明矩阵为一个点。
求mid值，即 ( (x1+x2)/2 , (y1+y2)/2 )
将mid值与target进行比较，来决定接下来取查询那些范围

· 如果target = mid 说明找到了目标值

· 如果target < mid，说明以mid为最小值的那块矩阵，不会有target， target在其他范围

· 如果target > mid，说明以mid为最大值的那块矩阵里，不会有target， target在其他范围里面
接下来对其他范围进行递归查询

代码：

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;

    }

}

巴特西

leetcode240 搜索二维矩阵 II

题目：

思路：

代码：

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

最新文章

热门文章