題目

解題概念

  • 此題簡單來說，就是要從一陣列 matrix 中，找出目標 target
  • 實際執行上，要從陣列的特性下手 :
    1. 對 Each Row 而言，最大值都位於最右方
    2. 對 Each Column 而言，最小值都位於最上方
    3. 故可推論出，搜尋起始點為右上方
  • 接著，主要迴圈的判斷方式為 :
    • 若 matrix[i][j] = target : 找到目標，回傳 true
    • 若 matrix[i][j] > target : 代表 matrix[i][j] 那列左方還有更小的元素，故 j -= 1
    • 若 matrix[i][j] < target : 代表 matrix[i][j] 那排下方還有更大的元素，故 i += 1

實際寫Code

  • 目標函式 : searchMatrix(matrix, target)
    • Input : matrix: List[List[int]]、target: int
    • Output : bool
  • 前置作業 : 
    1
    2
    3
    4
    5
    6
    i_len = len(matrix)
    j_len = len(matrix[0])

    # 設定好右上方元素 matrix[i][j] 為起始點
    i = 0
    j = j_len - 1
  • 主要迴圈 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    # 若 i 與 j 皆在合理範圍中
    while i < i_len and j >= 0:

        # 相等之狀況
        if matrix[i][j] == target :
            return True

        # 元素大於目標之狀況
        elif matrix[i][j] > target :
            j -= 1

        # 元素小於目標之狀況
        else : 
            i += 1

    # 若跑完迴圈仍未回傳 true，代表陣列 matrix 中無目標值 target，因此回傳 false
    return False