Problem :

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

Example 1 :

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
Output: true

Example 2 :

Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
Output: false

核心思維 :

1. 獲取矩陣的行數與列數
2. 檢查矩陣是否有效
3. 初始化行與列，即從右上角開始執行
4. 開始尋找目標值

• 若當前元素等於目標值則回傳true
• 若當前元素大於目標值則向左移動一列
• 若當前元素小於目標值則向下移動一行

5. 若搜尋結束仍未找到目標值則回傳false

程式碼 :

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //獲取矩陣的行數m和列數n
        int m = matrix.size();
        int n = matrix[0].size();
        //若矩陣的行數或列數小於1則回傳false
        if(n < 1 || m < 1){
            return false;
        }
        //設定row為0，column為n-1，即從矩陣的右上角開始
        int row = 0;
        int column = n - 1;
        //開始尋找目標值，直到row超過行數或column變成負數
        while((column >= 0) && (row < m)){
            //若當前元素等於目標值則回傳true
            if(matrix[row][column] == target){
                return true;
            }
            //若當前元素大於目標值則向左移動一列
            else if(matrix[row][column] > target){
                column--;
            }
            //若當前元素小於目標值則向下移動一行
            else{
                row++;
            }
        }
        //若未找到目標值則回傳false
        return false;
    }
};

結論 :

這題的目標是在已排序的陣列當中搜尋是否有目標值，從右上角開始搜尋，根據當前元素與目標值的大小關係決定往哪個方向移動，直到找到目標或遍歷完所有可能位置，適合用於大規模的有序陣列搜尋。