[LeetCode/Java] 215. Kth Largest Element in an Array

0. 문제

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

1. 문제 설명

• 정수 배열 nums와, 정수 k가 주어질 때, num의 원소 중 k번째로 큰 값을 반환하시오

2. 문제 풀이

2.1. 접근법

• 배열을 오름차순 정렬한 다음 뒤에서 k번째 값을 반환한다.

3. 코드

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

4. 결과

5. 개선점

5.1. 공간 복잡도 개선 : Heap 사용

• PriorityQueue를 사용해서 구현

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            q.offer(nums[i]);
        }
        
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > q.peek()) {
                q.poll();
                q.offer(nums[i]);
            }
        }
        
        return q.peek();
    }
}

• 결과