240. Search a 2D Matrix II

1.問題

• 判斷是否可以在矩陣中找到target, 矩陣的特性如下:

  • 每一row的排序為由左到右升冪

  • 每一col的順序為由上到下升冪

2.想法

• 提問:

• function header, parameter

• test input

• 說明想法

  • 由於此陣列的排列順序為左到右, 上到下ascending排序, 因此可以先從右上角開始, 與target比較, 如果該點大於target, 則左移該點; 如果該點小於target, 則下移該點

• 測試計算複雜度

3.程式碼

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0) {
            return false;
        }
        return search(matrix, target);
    }
private:
    bool search(vector<vector<int>>& matrix, int target){
        int col = matrix[0].size() - 1 ;
        int row = 0;
        while (row < matrix.size() &&
               col >= 0 ) {
            if (matrix[row][col] == target) {
                return true;
            }
            if (matrix[row][col] > target) {
                col--;
            } else if (matrix[row][col] < target) {
                row++;
            }
        }
        
        return false;
    }
};