成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Search a 2D Matrix 搜索二維矩陣

elisa.yang / 2646人閱讀

摘要：由于數(shù)組的特性，我們可以從二維數(shù)組的右上角出發(fā)，如果目標(biāo)小于該數(shù)，則向左移動左邊的數(shù)字肯定更小，而當(dāng)前列中所有數(shù)字都比該數(shù)字大。

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 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.
二分法 復(fù)雜度

時間 O(log(MN)) 空間 O(1)

思路

我們可以把二維數(shù)組想象成一個一維數(shù)組，第一行尾連著第二行頭，第二行尾連著第三行頭...同樣是有個最小值最大值，二分得到中間值，通過對中間值取?？梢缘玫綄?yīng)二維數(shù)組的下標(biāo)。這樣，該題就轉(zhuǎn)化為了一維有序數(shù)組二分搜索的題了。

注意

二分搜索的幾個邊界條件是min<=max，min=mid+1,max=mid-1

代碼 
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if(m == 0) return false;
        int n = matrix[0].length;
        int min = 0, max = m * n - 1;
        while(min <= max){
            int mid = min + (max - min) / 2;
            int row = mid / n;
            int col = mid % n;
            if(matrix[row][col] == target){
                return true;
            } else if (matrix[row][col] < target){
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
        return false;
    }
}

2018/2

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not matrix[0]:
            return False
        rows = len(matrix)
        cols = len(matrix[0])
        min, max = 0, rows * cols - 1
        while min <= max:
            mid = min + (max - min) // 2
            row = mid // cols
            col = mid % cols
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] < target:
                min = mid + 1
            elif matrix[row][col] > target:
                max = mid - 1
        return False
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. 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.
貪心法 復(fù)雜度

時間 O(N+M) 空間 O(1)

思路

雖說該方法叫貪心法不太得當(dāng)，但是貪心最能描述該方法的過程。由于數(shù)組的特性，我們可以從二維數(shù)組的右上角出發(fā)，如果目標(biāo)小于該數(shù)，則向左移動（左邊的數(shù)字肯定更小，而當(dāng)前列中所有數(shù)字都比該數(shù)字大）。如果該數(shù)比目標(biāo)小，則向下移動（下邊的數(shù)字肯定更大，而當(dāng)前行的所有數(shù)字逗比該數(shù)字?。＿@樣反復(fù)重復(fù)該過程就能找到目標(biāo)數(shù)。如果直到左下角都沒有該數(shù)，說明找不到該數(shù)。同樣的，這題也可以從左下角向右上角尋找。

代碼 
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix.length == 0){
            return false;
        }
        int i = 0, j = matrix[0].length - 1;
        while(i < matrix.length && j >= 0){
            int curr = matrix[i][j];
            if(curr == target){
                return true;
            // 比目標(biāo)小則向下
            } else if(curr > target){
                j--;
            // 比目標(biāo)大則向左
            } else {
                i++;
            }
        }
        return false;
    }
}

2018/2

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not matrix[0]:
            return False
        rows = len(matrix)
        cols = len(matrix[0])
        row, col = 0, cols - 1
        while row >= 0 and row < rows and col >=0 and col < cols:
            if matrix[row][col] > target:
                col -= 1
            elif matrix[row][col] < target:
                row += 1
            elif matrix[row][col] == target:
                return True
        return False

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64563.html

相關(guān)文章

  • leetcode 240. Search a 2D Matrix II

    摘要：代碼如下超時當(dāng)然了，這個方法不出意外，超時了思路二二分法查找我們采用二分法的思想，將矩陣分解為更小的矩陣從而每一次篩選確保能夠去除掉一個子矩陣范圍。從而我們可以將目標(biāo)值鎖定在左上方的子矩陣上。 題目要求 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has t...

    lanffy 評論0 收藏0

  • leetcode74. Search a 2D Matrix

    摘要：題目要求假設(shè)存在這樣一個二維數(shù)組，該數(shù)組從左到右，從上到下均遞增，且下一行第一個值比上一行最后一個值大?？傆?jì)的時間復(fù)雜度為，代碼如下二維二分法如何能之間在二維數(shù)組上使用二分法呢。 題目要求 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the foll...

    niuxiaowei111 評論0 收藏0

  • leetcode 48 Rotate Image

    摘要：題目詳情這道題目要求我們對一個正方形矩陣進(jìn)行順時針度的翻轉(zhuǎn)。并且要求不聲明額外的空間，不能新建二維數(shù)組。輸入數(shù)組旋轉(zhuǎn)后的輸入數(shù)組想法這道題因?yàn)橐笤谖弧Ｋ晕覀冃枰业揭环N解法，使得每次操作都是交換兩個元素的位置，最后實(shí)現(xiàn)整個矩陣的旋轉(zhuǎn)。 題目詳情 You are given an n x n 2D matrix representing an image.Rotate the ima...

    kgbook 評論0 收藏0

  • leetcode363. Max Sum of Rectangle No Larger Than K

    摘要：思路一暴力循環(huán)如果我們將矩陣中的每個子矩陣都枚舉出來，并計(jì)算其元素和，從而得出小于的最大值即可。 題目要求 Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k. E...

    nemo 評論0 收藏0

  • [Leetcode] Word Search I&amp;II 二維字符矩陣查找單詞

    摘要：復(fù)雜度時間空間為長度，為大小空間復(fù)雜度是是因?yàn)槲矣么嫘畔ⅲ粍討B(tài)地存當(dāng)前的路徑如果用來存信息的話空間復(fù)雜度就是時間復(fù)雜度對每個點(diǎn)都要作為起始點(diǎn)，對于每個起始點(diǎn)，拓展一次有四個可能性四個鄰居，要拓展次長度為。思路暴力搜索帶走。 Word Search I Given a 2D board and a word, find if the word exists in the grid. ...

    LuDongWei 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<