215. Kth Largest Element in an Array

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

Example 1:

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

Example 2:

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

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

1.QuickSort

最容易想到的方案就是排序后取对应位数，但是这种方式时间复杂度为O(nlogn)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

2.QuickSelect

可以借助快排的思想，当数组长度 - k = pivot右边的值个数时，可以认为pivot就是要找的数。这种方式平均时间复杂度为n + n/2 + n/4 + ... = 2n即O(n)

class Solution {

    static Random random = new Random(); 

    public int findKthLargest(int[] nums, int k) {
        return findKthLargest(nums, k, 0, nums.length);
    }

    public int findKthLargest(int[] nums, int k, int start, int end) {
        int pivot = random.nextInt(end - start) + start;
        int firstGePivot = start + 1;
        int pivotVal = nums[pivot];
        swap(nums, start, pivot);
        for (int i = start + 1; i < end; i++) {
            if (nums[i] < pivotVal) {
                swap(nums, i, firstGePivot++);
            }
        }
        swap(nums, start, firstGePivot - 1);

        int target = nums.length - k;
        if (firstGePivot - 1 == target) {
            return pivotVal;
        } else if (firstGePivot - 1 > target) {
            return findKthLargest(nums, k, start, firstGePivot - 1);
        } else {
            return findKthLargest(nums, k, firstGePivot, end);
        }
    }

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

}