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

215. Kth Largest Element in an Array

⭐ 문제

정수 배열 nums와 정수 k가 주어졌을 때, 배열에서 k번째로 큰 요소를 반환하세요

정렬된 순서에서 k번째로 큰 요소를 찾아야 하며, 중복되는 요소는 고려하지 않아야 합니다.

정렬을 하지않고 풀 수 있습니까?

🤔 접근 방향

Heap 자료구조를 사용하면 정렬을 하지 않고도 효율적으로 k번째로 큰 요소를 찾을 수 있으며, 공간 및 시간 효율성을 향상시킬 수 있기 때문에 이 문제를 해결하는 데 적합합니다.

✍️ 의사 코드

함수 k번째_최대값_찾기(nums, k):
    최소힙 = 빈 우선순위 큐
    
    배열의 각 요소에 대해 반복
        최소힙에 num 삽입
        
        만약 최소힙의 크기가 k보다 크다면:
            최소힙에서 가장 작은 요소 제거
    
    최소힙에서 가장 작은 요소 반환

✅ 나의 풀이

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();
            }
        }
        
        // 힙에서 루트 노드는 k번째로 큰 요소
        return minHeap.peek();
    }
}

🖥️ 결과

Runtime: 57 ms
Memory Usage: 56.6 MB