LeetCode 熱題 100 | 74. 搜索二維矩陣

大家好，今天我們來解決一道經典的算法題——搜索二維矩陣。這道題在 LeetCode 上被標記為中等難度，要求我們在一個滿足特定條件的二維矩陣中查找一個目標值。如果目標值在矩陣中，返回 true；否則，返回 false。下面我將詳細講解解題思路，并附上 Python 代碼實現。

---

問題描述

給定一個滿足以下兩個條件的 m x n 整數矩陣：

1. 每行中的整數從左到右按非嚴格遞增順序排列。
2. 每行的第一個整數大于前一行的最后一個整數。

你需要判斷一個整數 target 是否在矩陣中。

示例 1：

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
輸出：true

示例 2：

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
輸出：false

---

解題思路

核心思想

1. 二分查找：

   • 由于矩陣的每一行都是有序的，并且每行的第一個元素大于前一行的最后一個元素，整個矩陣可以看作是一個一維有序數組。
   • 因此，可以使用二分查找來高效地查找目標值。

2. 映射二維索引到一維索引：

   • 將二維矩陣的索引映射到一維數組的索引，方便進行二分查找。

---

Python代碼實現

def searchMatrix(matrix, target):""":type matrix: List[List[int]]:type target: int:rtype: bool"""if not matrix or not matrix[0]:return Falsem, n = len(matrix), len(matrix[0])  # 獲取矩陣的行數和列數left, right = 0, m * n - 1  # 初始化二分查找的左右邊界while left <= right:mid = (left + right) // 2  # 計算中間索引mid_value = matrix[mid // n][mid % n]  # 將一維索引映射到二維索引if mid_value == target:return True  # 找到目標值，返回 Trueelif mid_value < target:left = mid + 1  # 目標值在右側，移動左邊界else:right = mid - 1  # 目標值在左側，移動右邊界return False  # 未找到目標值，返回 False# 測試示例
print(searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3))  # 輸出: True
print(searchMatrix([[1,3,5,7],[10,11,16,20],[23,30,34,60]], 13))  # 輸出: False

---

代碼解析

1. 初始化邊界：

   • left 初始化為 0，right 初始化為矩陣的最后一個元素的索引 m * n - 1。

2. 二分查找：

   • 在 left <= right 的范圍內，計算中間索引 mid。
   • 將一維索引 mid 映射到二維索引 matrix[mid // n][mid % n]。
   • 如果 mid_value 等于目標值，直接返回 True。
   • 如果 mid_value 小于目標值，說明目標值在右側，將 left 移動到 mid + 1。
   • 如果 mid_value 大于目標值，說明目標值在左側，將 right 移動到 mid - 1。

3. 返回結果：

   • 如果未找到目標值，循環結束后返回 False。

---

復雜度分析

• 時間復雜度：O(log(m * n))，其中 m 是矩陣的行數，n 是矩陣的列數。二分查找的時間復雜度為 O(log(m * n))。
• 空間復雜度：O(1)，只使用了常數個額外空間。

---

示例運行

示例 1

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
輸出：true

示例 2

輸入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
輸出：false

---

總結

通過將二維矩陣的索引映射到一維索引，我們可以使用二分查找高效地查找目標值。這種方法不僅簡潔，而且效率非常高，適合處理類似的問題。希望這篇題解對大家有所幫助，如果有任何問題，歡迎在評論區留言討論！

關注我，獲取更多算法題解和編程技巧！