Kth Largest Element
Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Implement KthLargest class:
KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.
Example 1:
Input
["KthLargest", "add", "add", "add", "add", "add"][3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]
Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8
Constraints:
1 <= k <= 104
0 <= nums.length <= 104
-104 <= nums[i] <= 104
-104 <= val <= 104
At most 104 calls will be made to add.
It is guaranteed that there will be at least k elements in the array when you search for the kth element.
사실 이 문제를 풀지 못해서 정답을 보고 공부하는 방식으로 진행했다.
최소 힙
을 이용한다.import java.util.PriorityQueue;
public class KthLargest {
private int k; //1. k, 우선순위 큐는 계속 사용 -> 멤버 변수로 선언
private PriorityQueue<Integer> minHeap;
public KthLargest(int k, int[] nums) {
this.k = k;
minHeap = new PriorityQueue<>(k); //2. 최소 힙 선언,크기를 k로 고정
for (int num : nums) { //3. 기존의 값을 큐에 대입
add(num);
}
}
public int add(int val) {
minHeap.offer(val);
// 4. 최소 힙 크기가 k를 넘어가면 첫번째 값 반환, 제거
if (minHeap.size() > k) {
minHeap.poll();
}
// 5. 루트 값(K번째 큰 수) 반환
return minHeap.peek();
}
public static void main(String[] args) {
KthLargest kthLargest = new KthLargest(3, new int[]{4, 5, 8, 2});
System.out.println(kthLargest.add(3)); // returns 4
System.out.println(kthLargest.add(5)); // returns 5
System.out.println(kthLargest.add(10)); // returns 5
System.out.println(kthLargest.add(9)); // returns 8
System.out.println(kthLargest.add(4)); // returns 8
}
}
최소 힙을 사용, 크기를 k로 제한하면 루트 노드가 k번째 수라는데 나는 왜 이해를 못하는가.
질문 게시판에 올려야겠다. 힙 구조를 공부하고 페이지에 추가하겠다...
+ 2024.08.01 추가
import java.util.PriorityQueue();
//작은 수가 우선순위를 갖는다
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());