給定一個
m x n整數矩陣，每列由左到右升序排列，每列的第一個元素大於上一列的最後一個元素。判斷目標值target是否存在於矩陣中。
Example:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 Output: true
Intuition
TIP
把二維矩陣視為一個已排序的一維陣列，直接用二分搜尋。
- 因為每列的第一個元素大於上一列的最後一個元素，整個矩陣攤平後就是一個有序陣列
- 索引轉換：一維索引
mid對應到matrix[mid / n][mid % n]
Approaches
1. Two Binary Searches — O(log m + log n) / O(1)
- Idea: 先二分搜尋找到目標可能在哪一列，再在該列內二分搜尋
- Time:
O(log m + log n) - Space:
O(1)
Two Binary Searches Code
class Solution {
fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
val m = matrix.size
val n = matrix[0].size
// 找目標所在列
var top = 0
var bottom = m - 1
while (top <= bottom) {
val mid = top + (bottom - top) / 2
when {
target < matrix[mid][0] -> bottom = mid - 1
target > matrix[mid][n - 1] -> top = mid + 1
else -> {
// target 在 matrix[mid] 這一列
var left = 0
var right = n - 1
while (left <= right) {
val col = left + (right - left) / 2
when {
matrix[mid][col] == target -> return true
matrix[mid][col] < target -> left = col + 1
else -> right = col - 1
}
}
return false
}
}
}
return false
}
}⭐ 2. Single Binary Search (flattened matrix) — O(log(m * n)) / O(1)
- Idea: 將 m x n 矩陣視為長度 m*n 的有序陣列，直接二分搜尋
- Time:
O(log(m * n)) - Space:
O(1)
class Solution {
fun searchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
val m = matrix.size
val n = matrix[0].size
var left = 0
var right = m * n - 1
while (left <= right) {
val mid = left + (right - left) / 2
val midVal = matrix[mid / n][mid % n]
when {
midVal == target -> return true
midVal < target -> left = mid + 1
else -> right = mid - 1
}
}
return false
}
}🔑 Takeaways
- Pattern: 矩陣索引與一維索引的轉換
- Key trick:
row = index / cols,col = index % cols是矩陣類問題的基本轉換公式，讓你可以把任何有序矩陣當成一維陣列處理