[LeetCode] 215. 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?

 

 

Example 1:

Input: nums = [3, 2, 1, 5, 6, 4], k = 2

Output: 5

 

 

 

 

내 생각

 

주어진 정수 배열에서 k번쨰로 큰 요소를 찾는 문제이다. 

첫번째는 정렬을 이용하였는데, 더 알아보다가 정렬보다 최소 힙이 더 효율적이라고 하여 최소 힙으로도 구현해보았다.

모든 배열을 힙에 추가하고, 힙의 크기가 k를 넘어가면 가장 작은 요소를 제거해가면서 마지막에 남는 요소는 k번째 큰 요소가 된다  !!!

 

 

내 코드

1. 정렬 이용

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

 

2. 

class Solution {
    public int findKthLargest(int[] nums, int k) {
        //최소 힙
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        for (int num : nums) {
            minHeap.offer(num);
            // 힙의 크기가 k를 초과하면 가장 작은 요소를 제거
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }
}