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 = 2Output: 5

Example 2:

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

Note:

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

难度：medium

题目：找出在没有排序的数组中第K大的元素，注意是排序后的第K大的元素，不是第Ｋ个不同元素。

思路：快速排序

Runtime: 29 ms, faster than 36.08% of Java online submissions for Kth Largest Element in an Array.

Memory Usage: 38.8 MB, less than 51.09% of Java online submissions for Kth Largest Element in an Array.

class Solution {    public int findKthLargest(int[] nums, int k) {        int idx = -1;        k = nums.length - k;        for (int i = 0, j = nums.length - 1; i <= j && idx != k;) {            idx = quickSort(nums, i, j);            if (idx < k) {                i = idx + 1;            } else if (idx > k) {                j = idx - 1;            }        }                return nums[idx];    }        private int quickSort(int[] nums, int i, int j) {        int piovt = nums[i];        while (i < j) {            while (i < j && nums[j] >= piovt) {                j--;            }            nums[i] = nums[j];            while (i < j && nums[i] < piovt) {                i++;            }            nums[j] = nums[i];        }        nums[i] = piovt;                return i;    }}