215. 배열의 K번째 최대 요소

원제 링크

분치 방식

이 문제는 바로 빠른 정렬의 변종(물론 직접 정렬하고 출력도 가능)이지만, 여기서 사용하는 것은 빠른 정렬을 선택하여 빠른 정렬을 하는 과정에서 답을 찾을 수 있다.먼저 빠른 배열의 과정은 먼저 기준치 x를 선택한 다음에 x에 따라 수조 2를 >=x와 <=x의 두 구간(여기는 강순으로 하는 규칙)으로 나누어 귀속 처리하는 것이다.상술한 사고방식에 따라 우리는 두 개의 구간이 생길 수 있다는 것을 알고 있지만 답안은 그 중의 한 구간에만 존재한다. 답안이 존재하는 어느 구간만 선택하면 된다. 다른 구간은 처리할 필요가 없다. 지금 우리가 필요로 하는 답안이 구분된 구간 중 어느 구간을 어떻게 확정하는가?>=x의 구간의 길이와 k를 비교하면 답안이 어느 구간에 존재하는지 알 수 있다. 귀속은 이 구간만 선택하면 된다. 귀속 과정에서 구간의 길이가 1일 때 그 값은 우리가 원하는 답이다. 왜냐하면 매번 답안이 선택한 구간에 있다는 것을 보장하기 때문이다.

코드는 다음과 같습니다.

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums, 0, nums.length - 1, k);
    }

    public int quickSort(int[] nums, int l, int r, int k){
        if(l >= r) return nums[l];
        int i = l - 1, j = r + 1, x = nums[l + r >> 1];

        while(i < j){
            do ++i; while(nums[i] > x);
            do --j; while(nums[j] < x);
            if(i < j) swap(nums, i, j);
        }

        if(j - l + 1 >= k) return quickSort(nums, l, j, k);
        else return quickSort(nums, j + 1, r, k - (j - l + 1));
    }

    public void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

상술한 방식은 분치 알고리즘을 사용한다

쌓는 방식

C++의 priority_를 직접 사용할 수 있습니다.queue, 직접 쓰면 됩니다. 큰 루트 구축이 끝난 후 k-1번 삭제한 후 이 루트 요소가 답입니다.

코드는 다음과 같습니다.

class Solution {
public:
    int findKthLargest(vector& nums, int k) {
        priority_queue q;
        for(int i = 0; i < nums.size(); ++i) q.push(nums[i]);

        while(--k) q.pop();

        return q.top();
    }
};

다음은 수동으로 큰 뿌리를 쌓는 방식으로 쓴다

코드는 다음과 같습니다.

class Solution {
public:
    int res[10010];
    int findKthLargest(vector& nums, int k) {
        int len = nums.size();
        
        for(int i = 0; i < len; ++i) res[i + 1] = nums[i];

        for(int i = len / 2; i >= 1; --i) down(i, len);// down 

        while(--k){
            res[1] = res[len--];
            down(1, len);
        }

        return res[1];
    }

    void down(int u, int cnt){
        int t = u;
        if(u * 2 <= cnt && res[u * 2] > res[t]) t = u * 2;
        if(u * 2 + 1 <= cnt && res[u * 2 + 1] > res[t]) t = u * 2 + 1;

        if(u != t){//u != t down 
            swap(res[u], res[t]);
            down(t, cnt);
        }
    } 
};