[leetcode 378] Kth Smallest Element in a Sorted Matrix

leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

 

이진탐색이지만 매우 어려웠다.

 

문제:

row별 col별 오름차순 된 이차원 배열에서 오름차순으로 k번째 원소 찾기

 

접근:

 

1. 이진 탐색 사용: left는 matrix[0][0] (최솟값) right는 matrix[n-1][n-1] (최댓값)

2. mid 구하기 동일

3. 기준점: mid를 기준으로 mid보다 작거나 같은 값의 개수를 센다.

그 개수가 k보다 작다면 left = mid+1로, k보다 크거나 같다면 right = mid로 이동시킨다.

 

3-1. mid보다 작거나 같은 값 개수 세기

row는 0부터 col는 n-1부터 돌면서 matrix[row][col]<=m이면 row++; cnt+=(col+1)

 

 

다른 방법:

탐색이므로 insert와 search에 적은 비용이 소모되는 우선순위 큐를 사용해도 된다.

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        
        int n = matrix.length;
        
        int l = matrix[0][0], r=matrix[n-1][n-1];
        
        while(l<r){
            int mid = l + (r-l)/2;
            if(findSmallerOrEqual(matrix, mid, n) <k){
                l = mid+1;
            }else {
                r = mid;
            }
        }
        return l;
        //or return r;
        
    }
    
    public int findSmallerOrEqual(int[][] matrix, int mid, int len){
        int row = 0, col = len-1, cnt= 0;
        
        while(row<len && col >=0){
            if(matrix[row][col]<=mid){
                row++;
                cnt += (col+1);
            }else{
                col--;
            }
        }
        return cnt;
    }
}