[한번 지나] Lintcode 38. 2 차원 매트릭스 검색 II

효율 적 인 알고리즘 을 써 서 m 를 검색 하 다.×행렬 의 값, 이 값 이 나타 난 횟수 를 되 돌려 줍 니 다.
이 행렬 은 다음 과 같은 특성 을 가지 고 있다.
 
4. 567917. 각 줄 의 정 수 는 왼쪽 에서 오른쪽으로 정렬 된다
4. 567917. 각 열의 정 수 는 위 에서 아래로 정렬 된다
4. 567917. 각 줄 이나 각 열 에 중복 되 는 정수 가 없다
 
본보기
다음 행렬 을 고려 합 니 다:
[
    [1, 3, 5, 7],
    [2, 4, 7, 8],
    [3, 5, 9, 10]
]
target 제시 = 3, 귀환 2
도전 하 다.
O (m + n) 시간 복잡 도와 O (1) 추가 공간 요구
문제 풀이 사고 1:
우선 줄 마다 2 점 씩 찾 는 게 생각 났 어 요.시간 복잡 도 는 O (nlogn) 로 문제 의 모든 열 을 이용 하지 못 한 것 도 순 서 를 잘 정 하 는 조건 이 므 로 가장 좋 은 것 이 아니다.

class Solution {
public:
    /**
     * @param matrix: A list of lists of integers
     * @param target: An integer you want to search in matrix
     * @return: An integer indicate the total occurrence of target in the given matrix
     */
    int searchMatrix(vector> &matrix, int target) 
    {
        // write your code here
        int resNum = 0;
        for(int i=0 ; i< matrix.size() ; i++)
            if(binarySearch(matrix[i] , target) != -1)
                resNum++;
        
        return resNum;
    }
    
    int binarySearch(vector & vec , int target)
    {
        int l = 0;
        int r = vec.size()-1;
        
        return binarySearch(vec , l , r , target);
    }
    
    int binarySearch(vector & vec , int l , int r , int target)
    {
        if(l > r)
            return -1;
        
        int mid = (l+r) / 2;
        if(vec[mid] == target)
            return mid;
        else if(vec[mid] < target)
            return binarySearch(vec , mid+1 , r , target);
        else
            return binarySearch(vec , l , mid-1 , target);

    }
};

문제 풀이 사고 2:
만약 우리 가 문제 에서 준 그 예 를 관찰한다 면, 우 리 는 두 위치의 숫자 가 매우 특징 이 있 고, 왼쪽 아래 와 오른쪽 상단 의 수 를 발견 할 수 있다.예 를 들 어 오른쪽 상단 의 7 은 왼쪽 의 모든 수가 작 아 지고 아래 의 모든 수가 증가 하면 우 리 는 목표 수 와 비교 할 수 있다. 목표 수가 크 면 아래 를 찾 고 목표 수가 작 으 면 왼쪽 을 찾 을 수 있다.이렇게 하면 목표 수의 존재 여 부 를 판단 할 수 있다.코드 는 다음 과 같 습 니 다:

public class Solution {
    /**
     * @param matrix: A list of lists of integers
     * @param target: An integer you want to search in matrix
     * @return: An integer indicate the total occurrence of target in the given matrix
     */
    public int searchMatrix(int[][] matrix, int target) {
        // write your code here
        int row = matrix.length;
        int col = matrix[0].length;
        
        int res = 0;
        //        
        int i = row-1, j = 0;
        
        while(i >= 0 && j < col){
            if(matrix[i][j] == target){
                res++;
                i--;
            }else if(matrix[i][j] > target)
                i--;
            else
                j++;
        }
        
        return res;
    }
}