Skip to content

LeetCode: 74-Search a 2D Matrix 解題紀錄

Last Updated on 2022-03-30 by Clay

題目

Write an efficient algorithm that searches for a value target in an m x n integer matrix 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.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104

題目輸入一組二維陣列 matrix 以及一個目標值 target。若是 target 存在於 matrix 中返回 true,反之則回傳 false

matrix 是一個排序後的陣列,故有著以下特性:數字從左到右排序越來越大、高度則是越深越大。(可參考上方圖表)


解題思路

Brute Force 解法

這是最最直覺的解法之一了,遍歷陣列中的所有數值判斷是否存在目標值。


Brute Force 複雜度

透過題目我們知道陣列的尺寸為 m x n,故完整遍歷一次時間複雜度就是 O(m*n)。

Time complexityO(mn)
Space complexityO(1)


Brute Force 解法 C++ 範例程式碼

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // Finding
        for (int i=0; i<matrix.size(); ++i) {
            for (int j=0; j<matrix[0].size(); ++j) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }
        
        return false;
    }
};



Brute Force 解法 Python 範例程式碼

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # Finding
        for mat in matrix:
            for n in mat:
                if n == target:
                    return True
            
        return False
                



Brute Force 優化解法

不過除了直接暴力遍歷外,其實我們也可以直接比對每一行開頭的第一個數值,如果目標值的範圍落在第 i 行跟第 i+1 行開頭數值之間,即代表目標值可能存在第 i 行。(判斷到最後一行時就只能遍歷最後一行

而把第 i 行遍歷完如果沒找到,即意味著不需要再繼續尋找,所以這個方化是優化版的 Brute Force。


Brute Force 優化解法複雜度

我們需要掃過一次 m 的行數、再對長度為 n 的單行遍歷掃完;於是時間複雜度可以估計為 O(m+n)。

Time complexityO(m+n)
Space complexityO(1)


Brute Force 優化解法 C++ 範例程式碼

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // Init
        int i = 0;
        int j = 0;
        
        // Finding i
        for (i=0; i<matrix.size(); ++i) {
            if (i+1 >= matrix.size() || (target >= matrix[i][0] && target < matrix[i+1][0])) break;
        }
        
        // Finding j
        for (j=0; j<matrix[0].size(); ++j) {
            if (matrix[i][j] == target) return true;
        }
        
        return false;
    }
};



Brute Force 解法 Python 範例程式碼

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # Finding i
        for i in range(len(matrix)):
            if i+1 >= len(matrix) or (target >= matrix[i][0] and target < matrix[i+1][0]): 
                break
        
        # Finding j
        for j in range(len(matrix[0])):
            if matrix[i][j] == target:
                return True
        
        return False
                



二元搜索樹解法

另一種非常直覺的解法是,將組陣列從右上角開始搜尋起,將遍歷任務視為二元搜索樹的搜尋;如果當前搜索值大於目標值,則將搜索值往左挪一格(減少搜索值)、如果當前搜索值小於目標值,則將搜索值往下挪一格(增加搜索值)。

如果走到盡頭仍為找到目標值,回傳 false。


二元搜索樹優化解法複雜度

同樣地我們可能需要走過 m + n 的距離,故時間複雜度可以估計為 O(m+n)。

Time complexityO(m+n)
Space complexityO(1)


二元搜索樹解法 C++ 範例程式碼

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // Init
        int i = 0;
        int j = matrix[0].size() - 1;
        
        // Finding
        while (i < matrix.size() && j >= 0) {
            if (target == matrix[i][j]) return true;
            else if (target > matrix[i][j]) ++i;
            else --j;
        }
        
        return false;
    }
};



二元搜索樹解法 Python 範例程式碼

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # Init
        i = 0
        j = len(matrix[0]) - 1
        
        # Finding
        while i < len(matrix) and j >= 0:
            if target == matrix[i][j]: return True
            elif target > matrix[i][j]: i += 1
            else: j -= 1;
        
        return False
                

References


Read More

Leave a Reply取消回覆

Exit mobile version