leetcode74. Search a 2D Matrix

niuxiaowei111 发布于2019-08-15 10:41 / 439人阅读

摘要：题目要求假设存在这样一个二维数组，该数组从左到右，从上到下均递增，且下一行第一个值比上一行最后一个值大。总计的时间复杂度为，代码如下二维二分法如何能之间在二维数组上使用二分法呢。

题目要求

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

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
Given target = 3, return true.

假设存在这样一个二维数组，该数组从左到右，从上到下均递增，且下一行第一个值比上一行最后一个值大。要求从里面找到一个目标值，存在则返回true，否则返回false

一维二分法

熟悉二分法的知道，在一个有序的一维数组中，可以只用O(lgn)的时间复杂度就可以从中判读出目标值是否存在。我们可以先对第一列上的值进行一次二分法遍历，确定了行后再在行中进行第二次的二分法遍历。总计的时间复杂度为O(lgn），代码如下：

    public boolean searchMatrix(int[][] matrix, int target) {
        int row = matrix.length;
        if(row==0){
            return false;
        }
        int column = matrix[0].length;
        if(column==0){
            return false;
        }
        
        int leftPointer = 0, rightPointer=row-1;
        
        while(leftPointer<=rightPointer){
            int mid = (leftPointer+rightPointer) / 2;
            if(matrix[mid][0]<=target && matrix[mid][column-1]>=target){
                leftPointer = 0;
                rightPointer = column-1;
                while(leftPointer<=rightPointer){
                    int columnMid = (leftPointer + rightPointer) / 2;
                    if(matrix[mid][columnMid] == target){
                        return true;
                    }else if(matrix[mid][columnMid] < target){
                        rightPointer = columnMid-1;
                    }else{
                        leftPointer = columnMid + 1;
                    }
                }
                return false;
            }else if(target
二维二分法
如何能之间在二维数组上使用二分法呢。其实只要我们找到相应的左指针和右指针以及其对应的中间位置上的值即可。其实这个二维数组完全可以看成一个连续的一维数组，位于二维数组[i,j]位置可以看成一维数组中下标为[i*column+j].由此我们知道，左右指针对应中间节点在二维数组的下标为mid/column。代码如下：
public boolean searchMatrix2(int[][] matrix, int target){
    if(matrix==null || matrix.length==0 || matrix[0].length==0){
        return false;
    }
    int row = matrix.length;
    int column = matrix[0].length;
    int left = 0;
    int right = row*column-1;
    while(left<=right){
        int mid = (left + right) / 2;
        int tempVal = matrix[mid/column][mid%column];
        if(tempVal == target){
            return true;
        }else if(tempVal < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return false;
}

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

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

转载请注明本文地址：https://www.ucloud.cn/yun/67286.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
leetcode 240. Search a 2D Matrix II

摘要：代码如下超时当然了，这个方法不出意外，超时了思路二二分法查找我们采用二分法的思想，将矩阵分解为更小的矩阵从而每一次筛选确保能够去除掉一个子矩阵范围。从而我们可以将目标值锁定在左上方的子矩阵上。题目要求 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has t...

lanffy 2019-08-16 11:03 评论0 收藏0
[LeetCode] 304. Range Sum Query 2D - Immutable

Problem Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2). https://leetcode.com/static/i...s...

chinafgj 2019-08-16 13:43 评论0 收藏0
[LeetCode] 48. Rotate Image

Problem You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Note: You have to rotate the image in-place, which means you have to modify the input 2D mat...

Warren 2019-08-16 13:58 评论0 收藏0
leetcode 48 Rotate Image

摘要：题目详情这道题目要求我们对一个正方形矩阵进行顺时针度的翻转。并且要求不声明额外的空间，不能新建二维数组。输入数组旋转后的输入数组想法这道题因为要求在位。所以我们需要找到一种解法，使得每次操作都是交换两个元素的位置，最后实现整个矩阵的旋转。题目详情 You are given an n x n 2D matrix representing an image.Rotate the ima...

kgbook 2019-08-15 14:17 评论0 收藏0