leetcode 240. Search a 2D Matrix II

lanffy 发布于2019-08-16 11:03 / 2785人阅读

摘要：代码如下超时当然了，这个方法不出意外，超时了思路二二分法查找我们采用二分法的思想，将矩阵分解为更小的矩阵从而每一次筛选确保能够去除掉一个子矩阵范围。从而我们可以将目标值锁定在左上方的子矩阵上。

题目要求

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.
For 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.

假设存在这样一个矩阵，该矩阵从左至右以及从上到下的值均为由小到大排列。现在输入一个目标值，要求判断该矩阵中是否存在该值。

思路一：暴力递归

直观的来看我们肯定会从左上角开始判断，如果当前的值比目标值大，那么结束返回该值不存在，而如果当前的值比目标值小，则我们顺着行或是列继续查找。
代码如下：

    int column = 0;
    int row = 0;
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null || matrix.length == 0) return false;
        row = matrix.length;
        column = matrix[0].length;
        
        return searchMatrix2(matrix, target, 0, 0, row-1, column-1);
    }
    
    
    //超时
    public boolean searchMatrix(int rowIndex, int columnIndex, int target, int[][] matrix){
        if(rowIndex>=row || columnIndex>=column)return false;
        if(matrix[rowIndex][columnIndex] > target) return false;
        else if(matrix[rowIndex][columnIndex] == target) return true;
        return searchMatrix(rowIndex+1, columnIndex, target, matrix) || searchMatrix(rowIndex, columnIndex+1, target, matrix);
    }

当然了，这个方法不出意外，超时了~

思路二：二分法查找

我们采用二分法的思想，将矩阵分解为更小的矩阵从而每一次筛选确保能够去除掉一个子矩阵范围。我们以题目中的矩阵作为例子：

找到当前矩阵的中心下标，这里即为matrix[2][2]上的9，鉴于目标值5比9小，因此我们将矩阵分解为如下四块，并排除掉右下角的子矩阵，然后在剩余的三个矩阵中继续遍历。

  [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]

如果目标值比当前中心值更小，那么我们就可以排除左上角矩阵。

这个思路的代码如下：

    int column = 0;
    int row = 0;
    public boolean searchMatrix2(int[][] matrix, int target) {
        if(matrix==null || matrix.length == 0) return false;
        row = matrix.length;
        column = matrix[0].length;
        
        
        return searchMatrix2(matrix, target, 0, 0 ,row-1, column-1);
    }

    public boolean searchMatrix2(int[][] matrix, int target, int leftRow, int leftColumn, int rightRow, int rightColumn){
        if(leftRow==rightRow && leftColumn==rightColumn) return matrix[leftRow][leftColumn] == target;
        else if(leftRow > rightRow || leftColumn > rightColumn) return false;
        else if(target < matrix[leftRow][leftColumn] || target > matrix[rightRow][rightColumn]) return false;
        int midRow = (leftRow + rightRow) / 2;
        int midColumn = (leftColumn + rightColumn )/2;
        int midValue = matrix[midRow][midColumn];
        if(midValue == target) return true;
        else if(target < midValue){
            return searchMatrix2(matrix, target, leftRow, leftColumn, midRow-1, rightColumn) 
                    || searchMatrix2(matrix, target, midRow, leftColumn, rightRow, midColumn-1) ;
        }else{
            return searchMatrix2(matrix, target, leftRow, midColumn+1, rightRow, rightColumn)
                    || searchMatrix2(matrix, target, midRow+1, leftColumn, rightRow, midColumn);
        }
    }

思路三：换一个起点

当我们从左上角开始遍历时，我们会发现一次比较可以提供的信息实在是太少了。我们可以试着从左下角开始遍历看看是否能够提供更多的信息。还是以题目中给的矩阵作为例子：

从左下角比较的时，一旦目标值比当前值大，我们就将下标向右移动，一旦目标值比当前值小，我们就将下标向上移动。我们可以看见，因为从左下角开始遍历，那么每次的遍历都确保了我们的值一定比当前下标左侧的所有列的值大，也比当前下标下方所有行的值都大。从而我们可以将目标值锁定在左上方的子矩阵上。

这里给出的代码是从右上角开始遍历的，如下：

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

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/70990.html

[Leetcode] Search a 2D Matrix 搜索二维矩阵

摘要：由于数组的特性，我们可以从二维数组的右上角出发，如果目标小于该数，则向左移动左边的数字肯定更小，而当前列中所有数字都比该数字大。 Search a 2D Matrix I Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following pr...

elisa.yang 2019-08-14 12:34 评论0 收藏0
leetcode74. Search a 2D Matrix

摘要：题目要求假设存在这样一个二维数组，该数组从左到右，从上到下均递增，且下一行第一个值比上一行最后一个值大。总计的时间复杂度为，代码如下二维二分法如何能之间在二维数组上使用二分法呢。题目要求 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the foll...

niuxiaowei111 2019-08-15 10:41 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
[LintCode/LeetCode] Rotate Image

摘要：两种方法，转置镜像法和公式法。首先看转置镜像法原矩阵为转置后水平镜像翻转后所以，基本的思路是两次遍历，第一次转置，第二次水平镜像翻转变换列坐标。公式法是应用了一个翻转的公式如此翻转四次即可。二者均可，并无分别。 Problem You are given an n x n 2D matrix representing an image.Rotate the image by 90 de...

BenCHou 2019-08-14 15:22 评论0 收藏0