題目描述:給定一個 m x n 的整數矩陣 matrix,其中每一行從左到右遞增,每一列從上到下遞增(行列各自獨立排序,不像 LeetCode 74 那樣保證整體有序)。判斷目標值 target 是否存在於矩陣中。
解題思路:從矩陣的右上角開始搜尋(第 0 行、第 n-1 列)。此位置是該行的最大值、該列的最小值,具有以下性質:
matrix[row][col] == target:找到,回傳 true。matrix[row][col] > target:當前值太大,需要縮小,向左移動(col--),排除整列。matrix[row][col] < target:當前值太小,需要增大,向下移動(row++),排除整行。每次移動都排除一行或一列,最多執行 m + n 步,時間複雜度 O(m + n)。
時間複雜度:O(m + n) — 每次移動都排除一整行或一整列,最多移動 m 次(向下)加上 n 次(向左),共 m + n 步。
空間複雜度:O(1) — 只使用兩個指標 row 和 col,不需要額外記憶體。
1. Set row = 0, col = n - 1 (start at top-right corner) 2. While row < m and col >= 0: a. If matrix[row][col] == target: return True b. If matrix[row][col] > target: col -= 1 (move left) c. Else: row += 1 (move down) 3. Return False
方法一:逐行二分搜尋 對矩陣的每一行分別執行二分搜尋,找目標值。時間複雜度 O(m log n),空間複雜度 O(1)。比右上角法慢,但邏輯直觀,適合每行長度遠大於行數的情況。
方法二:分治法(Divide and Conquer) 選取矩陣中心元素,將矩陣分為四個象限。若中心等於 target 直接回傳;若中心小於 target,排除左上象限後遞迴搜尋其餘三個;若中心大於 target,排除右下象限後遞迴。時間複雜度為 O(n^{log₄ 3}) ≈ O(n^{1.58}),理論上介於 O(n) 和 O(n²) 之間,但實作複雜,且對 m × n 矩陣分析更複雜,實際較少使用。
m-1 行、第 0 列),搜尋邏輯應如何調整?為什麼左下角和右上角都可行,而左上角和右下角卻不行?