[Leetcode Top Interview 150] 215. Kth Largest Element in an Array

난이도 : medium

문제링크

• int array인 nums와 int값인 k가 주어진다
• nums 배열에서 k번째로 큰 값을 리턴하라

 

1. 접근법

• 유일한 값이 아닌, 중복된 값을 포함하여 리턴해야 함
• 최대 힙을 구현하여, k번째 pop된 값을 리턴하기

 

2. 의사코드

1. Heap 클래스 구현

public void push(int e) {
	arr[n++] = e;

    bubbleUp(n-1);
}

public void pop() {
	int top = arr[n-1];
    arr[0] = top;
    n--;
    bubbleDown(0);
    
    return top;
}

private void bubbleUp(int i) {
	if (i가 0보다 작거나 같으면) return; 
    	
	int parentIdx = (i-1)/2;    
    if (arr[i] > arr[parentIdx]) {
    	int temp = arr[i];
        arr[i] = arr[parentIdx];
        arr[parentIdx] = temp;
        bubbleUp(parentIdx);
    }    
}

private void bubbleDown(int i) {
	int child = i*2+1;
    int rightChild = i*2+2;
    
    if (child <= n-1) {
    	if (rightChild <= n-1 && arr[rightChild] > arr[child]) {
        	child = rightChild;
        }
        
        if (arr[child] > arr[i]) {
        	int tmp = arr[i];
            arr[i] = arr[child];
            arr[child] = tmp;
            bubbleDown(child);
        }
    }
}

 

3. 구현 코드

class Solution {
    private int[] arr;
    private int n;

    public int findKthLargest(int[] nums, int k) {        
        arr = new int[nums.length];
        map = new HashMap<>();
        n = 0;
        
        for (int i = 0; i < nums.length; i++) {
            push(nums[i]);
        }        
        
        int top = 0;
        while (k > 0) {
            top = pop();            
            k -= 1;
        }
    
        return top;
    }

    public void push(int i) {
        arr[n++] = i;
        
        bubbleUp(n-1);
    }

    public int pop() {
        int top = arr[0];        
        arr[0] = arr[n-1];
        n--;
        bubbleDown(0);

        System.out.println(top);
        
        return top;
    }

    private void bubbleUp(int i) {
        if (i <= 0) {
            return;
        }

        int parentIdx = (i-1)/2;
        if (arr[i] > arr[parentIdx]) {
            int tmp = arr[i];
            arr[i] = arr[parentIdx];
            arr[parentIdx] = tmp;
            bubbleUp(parentIdx);
        }
    }

    private void bubbleDown(int i) {
        int child = i*2+1;
        int rightChild = i*2+2;

        if (child <= n-1) {
            if (rightChild <= n-1 && arr[rightChild] > arr[child]) {
                child = rightChild;
            }

            if (arr[child] > arr[i]) {
                int tmp = arr[i];
                arr[i] = arr[child];
                arr[child] = tmp;
                bubbleDown(child);
            }
        }
    }
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 노드를 순회함
• 공간복잡도 : O(n) - 모든 노드를 생성해야 함

5. 개선점

• 잘 모르겠다. 왜 시간복잡도가 안좋은지..

 

6. 회고

• 다른 풀이를 보아도 비슷하게 풀었다