[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.

 

Example 1:

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

Example 2:

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

 

Constraints:

• 1 <= k <= nums.length <= 104
• -104 <= nums[i] <= 104

풀이)

1. 내가 푼 방법

public int findKthLargest(int[] nums, int k) {

    final PriorityQueue<Integer> pq = new PriorityQueue<>();
    for(int v : nums) {
        pq.offer(v);

        if(pq.size() > k) {
            pq.poll();
        }
    }
    return pq.peek();
}

1. 설명
 우선순위 큐를 사용했다는게 특징. Java의 우선순위 큐는 오름차순 정렬로 우선순위가 정해지기 때문에, 값이 입력될 때마다 오름차순으로 자동정렬된다. 따라서, k라는 최대 사이즈가 넘어가면, 마지막 값은 poll()로 빼내면 됨.

그리고 pq.peek()을 통해 pq의 마지막 값을 찾으면 된다.

 

2. 채점결과

3.시간복잡도

최선의 경우: O(N)

최악의 경우: O(N^2)

 

4. 공간복잡도

O(1)

 

2. 다른 사람 풀이(참고용)

    public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            final int j = partition(nums, lo, hi);
            if(j < k) {
                lo = j + 1;
            } else if (j > k) {
                hi = j - 1;
            } else {
                break;
            }
        }
        return nums[k];
    }

    private int partition(int[] nums, int lo, int hi) {
        int pivot = nums[hi];
        int i = lo;
        for (int j = lo; j < hi; j++) {
            if (nums[j] <= pivot) {
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, i, hi);
        return i;
    }

    private void swap(int[] a, int i, int j) {
        final int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    private boolean less(int v, int w) {
        return v < w;
    }

 

1. 설명

 선택정렬.

 파티션 함수 내에서 pivot으로 기준축을 잡고, pivot 기준으로 정렬을 함. 결국은 정렬을 통해 결과값을 찾는 방식.

 

2. 제출결과

3. 시간복잡도

O(n)