# 0215. Kth Largest Element in an Array
###### tags: `Leetcode` `Medium` `Priority Queue` `Sorting and Searching` `QuickSort`
Link: https://leetcode.com/problems/kth-largest-element-in-an-array/

## 思路
都是借鉴了 [347. Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/)的思路，一种方法是用PriorityQueue，一种是用QuickSort

### 思路一 QuickSort average: O(N) worst: O(N^2)
由于quicksort每次会确定一个元素的位置，因此只要某次划分的 q 为倒数第 k 个下标的时候，我们就已经找到了答案

### 思路二 PriorityQueue O(Nlogk）& O(k)
最小堆，保持堆里面只有k个元素，那么最后堆顶元素就是答案~

**这里要注意PriorityQueue的语法**

注意priorityQueue的定义，默认为最小堆，当a-b小于0时，comparator会回传-1，代表a比b小；当a-b大于0时，comparator会回传1，代表a比b大，这时候a就会被排到b的后面，因为priorityQueue默认为最小堆

## Code in Java
### 思路一

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int start = 0;
        int end = nums.length-1;
        int pivot = qsort(nums,start,end);
        while(true){
            if(pivot == k-1){
                return nums[pivot];
            }
            else if(pivot > k-1){
                end = pivot-1;
                pivot = qsort(nums, start, pivot-1);
            }
            else{
                start = pivot+1;
                pivot = qsort(nums, pivot+1, end);
            }
        }
    }
    public static void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
    public static int qsort(int[] nums, int start, int end){
        int pivot = (start+end)/2;
//        System.out.println(nums[pivot]+" "+pivot+" "+start+" "+end);
        swap(nums, pivot, start);
        int index = start;
        for(int i = start+1;i <= end;i++){
            if(nums[i]>=nums[start]){
                swap(nums, i, index+1);
                index++;
            }
        }
        swap(nums, start, index);
//        printArray(nums);
        return index;
    }
}

### 思路二

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0;i < nums.length;i++){
            if(i < k){
                pq.add(nums[i]);
            }
            else {
                int peek = pq.peek();
                if (nums[i] > peek && pq.size() == k) {
                    pq.poll();
                    pq.add(nums[i]);
                }
            }
        }
        return pq.peek();
    }
}

## Result
### 思路一
Runtime: 1 ms, faster than **98.45%** of Java online submissions for Kth Largest Element in an Array.
Memory Usage: 41.6 MB, less than **24.63%** of Java online submissions for Kth Largest Element in an Array.
### 思路二
Runtime: 5 ms, faster than **46.11%** of Java online submissions for Kth Largest Element in an Array.
Memory Usage: 42.3 MB, less than **9.70%** of Java online submissions for Kth Largest Element in an Array.