# 215    Kth Largest Element in an Array

## 215. [Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/description/)

## 1. Question

Find the **k**th largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,\
Given`[3,2,1,5,6,4]`and k = 2, return 5.

**Note:**\
You may assume k is always valid, 1 ≤ k ≤ array's length.

## 2. Implementation

**(1) Quick Select**

```java
class Solution {
    public int findKthLargest(int[] nums, int k) {
        return getKthNum(nums, 0, nums.length - 1, k - 1);
    }

    public int getKthNum(int[] nums, int start, int end, int k) {
        int pivot = partition(nums, start, end);

        if (pivot < k) {
            return getKthNum(nums, pivot + 1, end, k);
        }
        else if (pivot > k) {
            return getKthNum(nums, start, pivot - 1, k);
        }
        else {
            return nums[pivot];
        }
    }

    public int partition(int[] nums, int start, int end) {
        int mid = start + (end - start) / 2;

        swap(nums, mid, end);

        for (int i = start; i < end; i++) {
            if (nums[i] > nums[end]) {
                swap(nums, i, start);
                ++start;
            }
        }

        swap(nums, start, end);
        return start;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```

**(2) Heap**

```java
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int num : nums) {
            minHeap.add(num);

            if (minHeap.size() > k) {
                minHeap.remove();
            }
        }
        return minHeap.peek();
    }
}
```

## 3. Time & Space Complexity

**Quick Select**: 时间复杂度O(n), 空间复杂度O(1)

**Heap**: 时间复杂度O(n), 空间复杂度O(k)