[leetcode 240] Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n 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.

위 조건을 만족하는 이차원 배열에서 target값을 찾기

 

Example:

Consider the following 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] ]

 

 

문제 풀이:

- 일반적인 순회 방법 사용

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