LeetCode 215. Kth Largest Element in an Array 자바 문제 풀이

문제

Kth Largest Element in an Array - LeetCode

문제 해결 방법

-k번쨰로 큰 수를 찾는 문제

-내림차순(큰수부터 작은수)으로 정렬을 한다음, k번째 수를 리턴하면 된다.

-Arrays.sort와 comparator를 사용하면 쉽다.

1. 어레이를 정렬한다
2. k번쨰 수를 리턴한다

-PriorityQueue를 사용하는 방법도 있다.

1. PriorityQueue에 k만큼 넣는다.
2. k보다 많이 입력되면 가장 작은 수를 제거한다
3. 모두 입력되고 나면 가장 작은 수가 바로 k번째 수이다.

-만약 위 메서드들을 사용해서는 안된다고 한다면, 퀵솔트를 구현하라는 문제이다.

-퀵솔트는 엄밀하게 따지면, O(n log n)이지만, 평균적으로 O(n)이라고 표현한다. 즉, 위 문제는 퀵솔트를 구현할수 있는 능력이 있는지 묻는 문제이다.

https://github.com/eunhanlee/LeetCode_215_KthLargestElementinanArray_Solution.git

QuickSort시간복잡도: O(n log n), 공간복잡도: O(1)

import java.util.Random;

/**
 * 이 클래스는 퀵정렬을 사용하여 주어진 배열에서 k번째로 큰 요소를 찾는 메서드를 포함합니다.
 */
class Solution {
    private Random random = new Random();

    /**
     * 주어진 배열에서 k번째로 큰 요소를 찾습니다.
     *
     * @param nums 입력 배열
     * @param k k의 값
     * @return k번째로 큰 요소
     */
    public int findKthLargest(int[] nums, int k) {
        quickSortDescending(nums);  // 퀵정렬을 사용하여 배열을 내림차순으로 정렬합니다.
        return nums[k-1];  // 정렬된 배열에서 k번째로 큰 요소를 반환합니다.
    }

    /**
     * 주어진 배열을 퀵정렬을 사용하여 내림차순으로 정렬합니다.
     *
     * @param arr 정렬할 배열
     */
    public static void quickSortDescending(int[] arr) {
        quickSortDescendingRecur(arr, 0, arr.length - 1);
    }

    /**
     * 주어진 배열을 퀵정렬 알고리즘을 사용하여 내림차순으로 재귀적으로 정렬합니다.
     *
     * @param arr 정렬할 배열
     * @param left 분할의 왼쪽 인덱스
     * @param right 분할의 오른쪽 인덱스
     */
    private static void quickSortDescendingRecur(int[] arr, int left, int right) {
        while (left < right) {
            int pivotIndex = randomPartition(arr, left, right);  // 랜덤 분할을 사용하여 피벗 인덱스를 구합니다.
            if (pivotIndex - left < right - pivotIndex) {
                quickSortDescendingRecur(arr, left, pivotIndex - 1);  // 왼쪽 분할을 정렬합니다.
                left = pivotIndex + 1;  // 오른쪽 분할을 정렬하기 위해 왼쪽 포인터를 업데이트합니다.
            } else {
                quickSortDescendingRecur(arr, pivotIndex + 1, right);  // 오른쪽 분할을 정렬합니다.
                right = pivotIndex - 1;  // 왼쪽 분할을 정렬하기 위해 오른쪽 포인터를 업데이트합니다.
            }
        }
    }

    /**
     * 배열을 랜덤 분할하고 피벗 인덱스를 반환합니다.
     *
     * @param arr 분할할 배열
     * @param left 분할의 왼쪽 인덱스
     * @param right 분할의 오른쪽 인덱스
     * @return 피벗 인덱스
     */
    private static int randomPartition(int[] arr, int left, int right) {
        Random random = new Random();
        int randomIndex = random.nextInt(right - left + 1) + left;  // 범위 내에서 랜덤 인덱스를 생성합니다.
        swap(arr, randomIndex, right);  // 랜덤하게 선택된 요소를 오른쪽 끝 요소와 교환합니다.
        return partition(arr, left, right);  // 분할을 수행하고 피벗 인덱스를 반환합니다.
    }

    /**
     * 피벗 요소를 기준으로 배열을 분할하고 피벗 인덱스를 반환합니다.
     *
     * @param arr 분할할 배열
     * @param left 분할의 왼쪽 인덱스
     * @param right 분할의 오른쪽 인덱스
     * @return 피벗 인덱스
     */
    private static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];  // 오른쪽 끝 요소를 피벗으로 선택합니다.
        int i = left - 1;  // 작은 요소의 인덱스

        for (int j = left; j < right; j++) {
            if (arr[j] > pivot) {  // 현재 요소가 피벗보다 큰 경우
                i++;
                swap(arr, i, j);  // arr[i]와 arr[j]를 교환합니다.
            }
        }

        swap(arr, i + 1, right);  // 피벗 요소를 i+1 위치의 요소와 교환합니다.
        return i + 1;  // 피벗 인덱스를 반환합니다.
    }

    /**
     * 주어진 배열에서 두 요소를 교환합니다.
     *
     * @param arr 배열
     * @param i 첫 번째 요소의 인덱스
     * @param j 두 번째 요소의 인덱스
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];  // arr[i]와 arr[j]를 교환합니다.
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Arrays.sort와 comparator 시간복잡도: O(n log n), 공간복잡도: O(1)

import java.util.Arrays;
import java.util.Comparator;

public class Solution2 {
    /**
     * 주어진 배열에서 k번째로 큰 요소를 찾습니다.
     *
     * @param nums 입력 배열
     * @param k k의 값
     * @return k번째로 큰 요소
     */
    public int findKthLargest(int[] nums, int k) {
        Integer[] integerArray = Arrays.stream(nums)  // int[] 배열을 Integer[]로 변환합니다.
                .boxed()  // 각 요소를 Integer 래퍼로 박싱합니다.
                .toArray(Integer[]::new);  // Integer[]로 변환합니다.

        Arrays.sort(integerArray, Comparator.reverseOrder());  // 내림차순으로 정렬합니다.

        return integerArray[k-1];  // k번째로 큰 요소를 반환합니다.
    }
}

Arrays.sort 시간복잡도: O(n log n), 공간복잡도: O(1)

import java.util.*;

public class Solution3 {
    /**
     * 주어진 배열에서 k번째로 큰 요소를 찾습니다.
     *
     * @param nums 입력 배열
     * @param k k의 값
     * @return k번째로 큰 요소
     */
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);  // 배열을 오름차순으로 정렬합니다.

        return nums[nums.length-k];  // 정렬된 배열에서 끝에서 k번째 요소를 반환합니다.
    }
}

PriorityQueue 시간복잡도: O(n log k), 공간복잡도: O(K)

import java.util.*;

public class Solution4 {
    /**
     * 주어진 배열에서 k번째로 큰 요소를 찾습니다.
     *
     * @param nums 입력 배열
     * @param k k의 값
     * @return k번째로 큰 요소
     */
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();  // 우선순위 큐 생성

        for(int val : nums) {
            pq.offer(val);  // 우선순위 큐에 각 요소를 삽입합니다.

            if(pq.size() > k) {  // 큐의 크기가 k보다 크면 가장 작은 요소를 제거합니다.
                pq.poll();
            }
        }

        return pq.peek();  // 우선순위 큐에서 가장 작은 요소를 반환합니다.
    }
}