74. Search a 2D Matrix

Medium

Description

給定一個 m x n 整數矩陣，每列由左到右升序排列，每列的第一個元素大於上一列的最後一個元素。判斷目標值 target 是否存在於矩陣中。

Example:

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

Intuition#

把二維矩陣視為一個已排序的一維陣列，直接用二分搜尋。

因為每列的第一個元素大於上一列的最後一個元素，整個矩陣攤平後就是一個有序陣列
索引轉換：一維索引 mid 對應到 matrix[mid / n][mid % n]

Approaches#

1: 兩次二分搜尋#

概念: 先二分搜尋找到目標可能在哪一列，再在該列內二分搜尋
時間複雜度: O(log m + log n)
空間複雜度: O(1)

兩次二分搜尋程式碼

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: 一次二分搜尋（攤平矩陣）#

概念: 將 m x n 矩陣視為長度 m*n 的有序陣列，直接二分搜尋
時間複雜度: O(log(m * n))
空間複雜度: 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: 矩陣索引與一維索引的轉換
關鍵技巧: row = index / cols, col = index % cols 是矩陣類問題的基本轉換公式，讓你可以把任何有序矩陣當成一維陣列處理