LeetCode 74 & 240 Search a 2D Matrix I,II

原创

大学里的混子

修改于 2018-10-27 18:51:11

4800

修改于 2018-10-27 18:51:11

文章被收录于专栏：LeetCode

74. Search a 2D Matrix

74. Search a 2D Matrix
            DescriptionHintsSubmissionsDiscussSolution
    Pick One
    Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

    Integers in each row are sorted from left to right.
    The first integer of each row is greater than the last integer of the previous row.
    Example 1:

    Input:
    matrix = [
            [1,   3,  5,  7],
            [10, 11, 16, 20],
            [23, 30, 34, 50]
            ]
    target = 3
    Output: true
    Example 2:

    Input:
    matrix = [
            [1,   3,  5,  7],
            [10, 11, 16, 20],
            [23, 30, 34, 50]
            ]
    target = 13
    Output: false

一个矩阵，每一行都是递增顺序，并且下一列比上一列的最大值要大。给定一个目标值，判断这个target是否在这个矩阵中。

同样的给出两种解法

解法一：

从第一列中采用二分搜索找到合适的行，再在这一行中采用二分搜索法找到合适的列即可

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0||matrix[0].length == 0) return false;
    if (target<matrix[0][0]||target>matrix[matrix.length-1][matrix[0].length-1]) return false;
    int row = searchMatrix_BS1_hepler(matrix,0,matrix.length-1,target);
    return searchMatrix_BS2_helper(matrix,0,matrix[0].length-1,target,row);
}

public boolean searchMatrix_BS2_helper(int[][] matrix,int left,int right,int target,int row){
    int mid = (right -left)/2 + left;
    if (left>right) return false;
    if (target == matrix[row][mid]) return true;
    if (target>matrix[row][mid]) {
        left = mid+1;
        return searchMatrix_BS2_helper(matrix,left,right,target,row);
    } else {
        right = mid-1;
        return searchMatrix_BS2_helper(matrix,left,right,target,row);
    }
}

public int searchMatrix_BS1_hepler(int[][] matrix,int left,int right,int target){
    int mid = (right -left)/2 + left;
    if (target == matrix[mid][0]){
        return mid;
    }else if (target>matrix[mid][0]){
        if (target <= matrix[mid][matrix[0].length-1]){
            return mid;
        } else {
            left = mid+1;
            return searchMatrix_BS1_hepler(matrix,left,right,target);
        }
    }else if (target<matrix[mid][0]){
        if (target >=matrix[mid-1][0]){
            return mid-1;
        }else {
            right = mid -1;
            return searchMatrix_BS1_hepler(matrix,left,right,target);
        }
    }
    return -1;
}

这种方法不是直接的，就当做是练习一下在矩阵中使用二分查找法了。

解法二：

更加直接的解法，其实这就是一个一维有序的数组分为几段后变成了二维数组，所以就采用一维数组的二分查找法就可以很容易的写出本题目的solution。

public boolean searchMatrix(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0||matrix[0].length == 0) return false;
    if (target<matrix[0][0]||target>matrix[matrix.length-1][matrix[0].length-1]) return false;
    return searchMatrix_helper(matrix,target,0,matrix.length*matrix[0].length-1);
}

public boolean searchMatrix_helper(int[][] matrix, int target,int left,int right){
    if (left > right ) return false;
    int mid = (right -left)/2+left;
    int row = mid/matrix[0].length;
    int col = mid - matrix[0].length*row;
    if (target == matrix[row][col]) return true;
    if (target>matrix[row][col]) return searchMatrix_helper(matrix,target,mid+1,right);
    else return searchMatrix_helper(matrix,target,left,mid-1);
}

240.Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following 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]
]

Given target = 5, return true.

Given target = 20, return false.

题目大意：一个矩阵，从左到右，从上到下，都是递增的顺序，给定一个目标值target，问在这个矩阵中能否找到这样的一个target。

观察矩阵可以发现，将这个target值与右上角的值相比较，如果target大于这个值，那么target若存在则绝对不可能在这一行的左边的数里面，同理可以知道，如果target小于这个值，那么target若存在则绝对不可能在这一列的下面的数里面。这样一步一步的最小目标区域即可，注意循环的退出条件，和递归的退出条件，都是放row或者col的值超出范围终止。

解法一：

递归解法：

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0||matrix[0].length == 0) return false;
        if (target<matrix[0][0]||target>matrix[matrix.length-1][matrix[0].length-1]) return false;
        return searchMatrix(matrix,target,0,matrix[0].length-1);
    }
    
    public boolean searchMatrix(int[][] matrix, int target,int row ,int col){
        if (row>=matrix.length||col<0) return false;
        if (matrix[row][col] == target) return true;
       
        if (matrix[row][col] < target) {
            return searchMatrix(matrix,target,row+1,col);
        }else {
            return searchMatrix(matrix,target ,row,col-1);
        }
    }

解法二：

非递归解法：

    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0||matrix[0].length==0) return false;
        int row = 0,col = matrix[0].length-1;
        while (row<matrix.length&&col>=0){
            if (matrix[row][col]>target){
                col--;
            }else if (matrix[row][col]<target){
                row++;
            }else {
                return true;
            }
        }
        return false;   
    }

总结:

矩阵中的查找法要充分利用矩阵的特征，将其转为我们熟知的查找法。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

登录后参与评论

0 条评论

热度