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.lengthn == matrix[i].length1 <= 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 complexity | O(mn) |
| Space complexity | O(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 complexity | O(m+n) |
| Space complexity | O(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 complexity | O(m+n) |
| Space complexity | O(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