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.
难度：medium
题目：找出在没有排序的数组中第 K 大的元素，注意是排序后的第 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;
}
}