[ Top Interview 150 ] 215. Kth Largest Element in an Array

문제

215. Kth Largest Element in an Array

 Given an integer array nums and an integer k, return the k-th largest element in the array.

 Note that it is the k-th largest element in the sorted order, not the k-th distinct element.

 Can you solve it without sorting?

• Input : nums, k
• Output : nums에서 k번째로 큰 수
• Condition : Sorting 없이 풀어보기

알고리즘 전략

• 방법 1. Sorting 이용

  • JDK에서 제공하는 Arrays.sort()를 이용

• 방법 2. Java에서 제공하는 PriorityQueue를 사용

  • 모든 원소를 PriorityQueue에 넣은 후 k번 원소를 꺼내는 방식

답안 1. Sorting 이용

• Time complexity : $O(nlogn)$

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

답안 2. PriorityQueue 이용

• Time complexity : $O(nlogn)$

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
        
        for (int i = 0; i < nums.length; i++) {
            queue.add(nums[i]);
        }
        
        for (int i = 0; i < k - 1; i++) {
            queue.remove();
        }
        
        return queue.remove();
    }
}