leetcode top interview 150 | Kth Largest Element in an Array | PriorityQueue

 

Question

 

정수배열이 주어질때 k번째로 큰 수를 리턴 

 

 

Accepted Code - Sorting

import java.util.*;
class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        int answer = 0;
        int idx = nums.length - 1;
        while(k-- > 0){
            answer = nums[idx--];
        }
        return answer;
    }
}

 

정렬을 한번 수행하고 k를 감소시켜가며 배열의 끝에 있는 값을 저장한다.

시간복잡도는 Arrays.sort()로 O(n log n)이 소요된다. Arrays.sort는 이전엔 퀵소트 방식을 사용했지만 Java 7이상부터는 병합정렬과 선택정렬을 활용한 방식으로 변경되었다고 한다. 

 

 

Accepted Code - PriorityQueue

import java.util.*;
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
        for(int num : nums){
            queue.offer(num);
        }
        while(--k > 0){
            queue.poll();
        }
        int answer = queue.poll();
        return answer;
    }
}

 

Solve

 

최대힙을 구성해서 k개수만큼 poll()하고 가장 앞에 있는 값을 poll()해서 리턴해주는 방식이 떠올랐다. 

Heap(Binary Heap) 

1. 부모노드의 값이 자식보다 크거나 같은 경우면서 완전이진트리인 구조로, 완전이진트리는 마지막 레벨을 제외한 노드들은 전부 채워져있고 마지막 레벨에 있는 노드들은 왼쪽부터 차례대로 채워져있는 트리구조이다.

2. 모든 노드가 자식노드 보다 크거나 같은 구조를 최대힙, 자식노드 보다 작거나 같으면 최소힙 구조라한다.

3. 우선순위가 가장 높은 요소를 삭제하거나 반환하는 연산 시 O(1)의 시간복잡도가 소요된다.

 

최대힙(Max Heap)을 구성하기 위해 우선순위 큐 생성 시 Collections.reverseOrder()로 최대값이 맨 앞으로 유지될 수 있도록 설정해줬다.

nums를 순회하며 모든 값을 큐에 넣어주고 while문을 통해 k번째 전까지 최대값들을 제거하여 큐의 맨 앞에 k번째로 큰 수가 올 수 있도록 한다. 

 

 

https://leetcode.com/problems/kth-largest-element-in-an-array/description/?envType=study-plan-v2&envId=top-interview-150 

Kth Largest Element in an Array - LeetCode