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

elisa.yang 發布于2019-08-14 12:34 / 2644人閱讀

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

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.

二分法 復雜度

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

思路

我們可以把二維數組想象成一個一維數組，第一行尾連著第二行頭，第二行尾連著第三行頭...同樣是有個最小值最大值，二分得到中間值，通過對中間值取模可以得到對應二維數組的下標。這樣，該題就轉化為了一維有序數組二分搜索的題了。

注意

二分搜索的幾個邊界條件是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.

貪心法 復雜度

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

思路

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

代碼

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;
            // 比目標小則向下
            } else if(curr > target){
                j--;
            // 比目標大則向左
            } 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

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/64563.html

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
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 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
leetcode363. Max Sum of Rectangle No Larger Than K

摘要：思路一暴力循環如果我們將矩陣中的每個子矩陣都枚舉出來，并計算其元素和，從而得出小于的最大值即可。題目要求 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 2019-08-16 17:57 評論0 收藏0
[Leetcode] Word Search I&II 二維字符矩陣查找單詞

摘要：復雜度時間空間為長度，為大小空間復雜度是是因為我用存信息，只動態地存當前的路徑如果用來存信息的話空間復雜度就是時間復雜度對每個點都要作為起始點，對于每個起始點，拓展一次有四個可能性四個鄰居，要拓展次長度為。思路暴力搜索帶走。 Word Search I Given a 2D board and a word, find if the word exists in the grid. ...

LuDongWei 2019-08-14 14:06 評論0 收藏0