[LeetCode] 240. Search a 2D Matrix II

문제 URL : https://leetcode.com/problems/search-a-2d-matrix-ii/

Search a 2D Matrix II - LeetCode

 

문제 접근법:  배열안에 타겟이 존재하는지 구하는문제입니다.

왼쪽에서 오른쪽 위에서 아래로 정렬이 되어있다고합니다.

솔직히 n*m 으로도 사이즈가 작아서 O(nm)에 풀릴수있을거라생각했는데 시간초가 나더군요

n+m 으로 구할수도 있는 문제긴하지만

빠르게 푸는것도 중요하다 생각되서 nlog(m) 의 시간복잡도를 알려드리려합니다.

 

소스코드 : 

 

class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int n=matrix.size();
    int m = matrix[0].size();
    int y=-1,x=-1;
    vector<int> rv,cv;
    for(int i=0;i<n;i++){
        int idx = lower_bound(matrix[i].begin(),matrix[i].end(),target)-matrix[i].begin();
        if(idx<m&&matrix[i][idx]==target){
            return true;
        }
    }
    return false;
}
};

 

 

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.