Kth Largest Element in an Array - LeetCode
Can you solve this real interview question? Kth Largest Element in an Array - Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct eleme
leetcode.com
정수 배열 num과 정수 k가 주어지면 배열에서 k번째로 큰 요소를 반환합니다.
k번째 고유 요소가 아니라 정렬된 순서에서 k번째로 큰 요소라는 점에 유의하세요.
+ 정렬하지 않고 풀 수 있는지도 물어봅니다!
Example 1:
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Example 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
문제 접근
배열에서 k번째로 큰 요소를 반환하는 것입니다.
그런제 정렬을 하지 않고 풀라고 합니다.
그럼 Heap을 사용하는 PriorityQueue를 사용해서 풀 수 있을것 같습니다.
PriorityQueue는 Defalute가 오름차순 정렬이기 때문에
람다식을 통해 Comparator를 구현하였습니다.
이후 k번째까지 loop를 돌면서 ret에 값을 담아 리턴하였습니다.
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>(((o1, o2) -> o2 - o1));
for (int num : nums) {
pq.add(num);
}
int ret = -1;
for (int i = 0; i < k; i++) {
ret = pq.poll();
}
return ret;
}
느낀점
PriorityQueue를 잘활용하면 삽입과 삭제를 O(log N)안에 할 수 있습니다.
상황에 따라 잘 활용해야겠습니다!
'LeetCode' 카테고리의 다른 글
[LeetCode] 133. Clone Graph (0) | 2023.09.14 |
---|---|
[LeetCode] 373. Find K Pairs with Smallest Sums (0) | 2023.09.12 |
[LeetCode] 211. Design Add and Search Words Data Structure[재도전중] (0) | 2023.09.11 |
[LeetCode] 208. Implement Trie (Prefix Tree) (0) | 2023.09.10 |
[LeetCode] 199. Binary Tree Right Side View (0) | 2023.09.07 |