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 element.

Can you solve it without sorting?

풀이

요구사항: 정렬없이 nums 배열에서 k번째로 큰 수를 구하시오.

• 예제 1
  • nums = [3, 2, 1, 5, 6, 4], k = 2
  • output: 5
  • nums 배열에서 2번째로 큰 수는 5이다.
• 정렬말고 다른 방법은 heap을 이용하는 방법이 있다. heap에 nums의 원소들을 -를 붙여 삽입하고 k번 제거하면 된다.

수도 코드

answer = 0
pq = 우선순위 큐 생성

for (nums의 원소들 num):
	pq에 -1 * num을 추가한다

for k번 반복:
	answer = pq에서 제거한다

return answer

Solution(Runtime: 57ms)

import java.util.*;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (var e: nums) {
            pq.add(-e);
        }

        for (int i = 0; i < k; i++) {
            answer = pq.poll();
        }
        return -answer;
    }
}

• 시간복잡도: O(nlogn) 소요