[C] LeetCode 215. Kth Largest Element in an Array

 

문제

번역

정수 배열 nums와 정수 k가 주어질때, array에서 k번째로 가장 큰 원소를 반환해라.

k번째 수는 정렬된 순서에서 k번째로 큰 수를 말하며, k번째의 구별되는 원소가 아니다. 정렬없이 구현해라.

접근 방법과 소스코드

대표적인 maxheap을 사용하는 문제이다.

입력받은 수로 maxheap을 구성한다. 그러면 heap의 root는 첫번째로 가장 큰 수가 있을 것이다.

이걸 k-1번 만큼 heap에서 pop을 하면 maxheap의 root는 k번째로 가장 큰 수가 담겨 있을 것이다.

우린 이걸 pop 해서 반환해주면 된다.

 

int heap[100001];
int rsp = 0;

void swap(int* a, int* b) {
    int t = *a;
    *a= *b;
    *b = t;
}

void push(int x) {
    heap[++rsp] = x;
    int ch = rsp, pa=rsp/2;
    while(ch > 1 && heap[pa] < heap[ch]) {
        swap(&heap[pa], &heap[ch]);
        ch = pa;
        pa = ch/2;
    }
}

int pop() {
    int r = heap[1];
    swap(&heap[1], &heap[rsp]); rsp--;
    int pa = 1;
    int ch = 2*pa;
    ch = (ch+1 <= rsp && heap[ch] < heap[ch+1]) ? ch+1 : ch;
    while(ch <= rsp && heap[pa] < heap[ch]) {
        swap(&heap[pa], &heap[ch]);
        pa = ch;
        ch = 2*pa;
        ch = (ch+1 <= rsp && heap[ch] < heap[ch+1]) ? ch+1 : ch;
    }
    return r;
}

int findKthLargest(int* nums, int numsSize, int k) {
    rsp=0;
    for(int i=0;i<numsSize;i++) push(nums[i]);
    int ret=0;
    for(int i=0;i<k;i++) {
        ret = pop();
    }
    return ret;
}

 

swap은 배열에서 두 수를 교환하기 위한 함수이다.

push는 heap에 새로운 값 x를 넣는다. 배열의 맨 마지막에 넣고, 여기서부터 맨 위까지 heapify(max/minheap의 조건을 만족할때까지 swap을 하는 함수내지 기능)해주면 된다.

pop의 경우 heap의 root를 잠시 보관해둔다. 해당 수를 지우기 위해 배열의 가장 마지막 원소와 swap을 진행하고, root에서부터 배열의 맨 마지막까지 heapify 해주면 된다. 이때, 자식은 왼쪽 노드와 오른쪽 노드 중 더 큰 노드로 결정한다.

 

그 뒤 nums 배열을 heap에 넣어주고, k번 pop해서 그 수를 반환한다.