leetcode74. Search a 2D Matrix

niuxiaowei111 發布于2019-08-15 10:41 / 441人閱讀

摘要：題目要求假設存在這樣一個二維數組，該數組從左到右，從上到下均遞增，且下一行第一個值比上一行最后一個值大。總計的時間復雜度為，代碼如下二維二分法如何能之間在二維數組上使用二分法呢。

題目要求

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;
}

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Matrix 阿里云領券74一年服務器 modelview matrix php74

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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