大廠面試真題題解：搜尋二維矩陣

寫出一個高效的算法來搜尋 m × n矩陣中的值。

這個矩陣具有以下特性：

• 每行中的整數從左到右是排序的。
• 每行的第一個數大于上一行的最後一個整數。

線上評測位址：

領扣題庫官網

樣例 1:

輸入: [[5]],2
        輸出: false
        
        樣例解釋: 
  沒有包含，傳回false。           

樣例 2:

輸入:  
[
  [1, 3, 5, 7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
],3
        輸出: true
        
        樣例解釋: 
        包含則傳回true。           

解題思路：

題目提到，給定的數組已經排序，若是一個一維數組，直接一次二分查找即可。現在題目給了一個二維數組，那麼處理一下數組的下标，仍然按照一維數組二分即可。

二分查找常用于查找有序數組中目标數target的位置，用left和right記錄target所在的區間端點，每次将區間的中間位置值和target作比較，然後移動區間端點。

算法流程：

• 将數組matrixi下标轉換為 i*col + j， 問題即轉換為一維數組二分查找問題
• 将區間指派為整個數組區間（left = 0, right = n*m - 1），取中間位置mid
• 若a[mid] < target，則将區間縮小到原區間的右區間(left = mid + 1)
• 若a[mid] > target，則将區間縮小至原區間的左區間(right = mid)
• 若a[mid] = target，傳回true

• 當left >= right 時，若a[right] = target則傳回true, 否則傳回false

  複雜度分析：

• 時間複雜度：O(log(nm))
• 即将二維數組看作一個n*m大小的一維數組，二分查找值。
• 空間複雜度：O(1)

• 查找不需要開辟新的空間，隻需在原數組基礎上進行查找即可

  代碼：

public class Solution {
    /**
     * @param matrix, a list of lists of integers
     * @param target, an integer
     * @return a boolean, indicate whether matrix contains target
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix.length;
        int col = matrix[0].length;
        int left = 0, right = n*col - 1;
        
        while(left < right){
            int mid = (right + left) / 2;
            if(matrix[mid/col][mid%col] == target){
                return true;
            }
            else if(matrix[mid/col][mid%col] > target){
                right = mid;
            }
            else{
                left = mid + 1;
            }
        }
        
        if(matrix[right/col][right%col] == target){
            return true;
        }
        
        return false;
    }
}           

更多題解參考：

九章官網Solution