leetcode link

Description

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가 주어질 때, 배열에서 k번째로 큰 요소를 반환합니다.

이때 k번째로 큰 요소는 정렬된 순서에서의 k번째 요소를 의미하며, 중복되지 않는 k번째 요소를 의미하지는 않습니다.

정렬 없이 이 문제를 해결할 수 있나요?

예시 1:

입력: nums = [3,2,1,5,6,4], k = 2
출력: 5

예시 2:

입력: nums = [3,2,3,1,2,4,5,5,6], k = 4
출력: 4

제약 조건:

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

Solution

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        var pq = new PriorityQueue<Integer>(Collections.reverseOrder());

        for (int num : nums) {
            pq.add(num);
        }

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

        return result;
    }
}

Solution 2

Quck Select 알고리즘을 사용해서 문제를 푸는 방법이 있습니다.

Quick Select 알고리즘은 배열에서 k번째로 큰 (또는 작은) 요소를 빠르게 찾는 방법입니다. 이 알고리즘은 Quick Sort의 아이디어를 기반으로 하며, 전체 배열을 정렬하지 않고도 특정 순위의 요소를 찾을 수 있어 효율적입니다.

알고리즘 선능은 최선의 O(n)이고 최악은 O(n^2) 입니다. 최악을 방지하기 위해서 random으로 피벗을 정합니다.

이 코드에서는 다음과 같은 절차로 Quick Select를 구현합니다:

1. 변환된 인덱스 계산: k번째로 큰 요소를 찾기 위해, 배열의 길이에서 k를 빼서 변환된 인덱스를 계산합니다. 이는 정렬될 때 k번째로 큰 요소가 배열에서 어디에 위치해야 하는지 결정합니다.

2. 분할 (Partitioning): 배열을 두 부분으로 나누는데, 한 부분에는 피벗(pivot)보다 작은 요소가, 다른 부분에는 피벗보다 큰 요소가 위치합니다. 이 과정에서 피벗의 최종 위치가 결정됩니다.

3. 재귀 (Recursion): k가 피벗의 인덱스와 같다면, 피벗이 k번째로 큰 요소입니다. k가 피벗 인덱스보다 작으면, 왼쪽 부분 배열에서 탐색을 계속합니다. 반대로 k가 딼벗 인덱스보다 크면, 오른쪽 부분 배열에서 탐색을 계속합니다.

4. 종료 조건: 왼쪽 또는 오른쪽 부분 배열에서 원하는 k번째 요소를 찾거나, 탐색 범위가 더 이상 나눌 수 없을 때까지 이 과정을 반복합니다.

이렇게 Quick Select는 피벗을

class Solution {
    public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int pivotIndex = partion(nums, left, right);

            // 탐색 범위를 줄인다
            if (k == pivotIndex)
                return nums[k];
            else if (k < pivotIndex)
                right = pivotIndex - 1;
            else
                left = pivotIndex + 1;
        }
        return -1;
    }

    int partion(int[] nums, int left, int right) {
        swap(nums, left, new Random().nextInt(right - left + 1) + left);
        int pivotIndex = left;
        int pivot = nums[pivotIndex];
        for (int i = left + 1; i <= right; i++) {
            if (nums[i] < pivot)
                swap(nums, i, ++pivotIndex);
        }
        swap(nums, left, pivotIndex);

        return pivotIndex;
    }

    void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}