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.
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.
一刷
Quick select
最好的情况下：
Discard half each time: n+(n/2)+(n/4)..1 = n + (n-1) = O(2n-1) = O(n), because n/2+n/4+n/8+..1=n-1.
原理是每次随机取一个pivot, 然后把大于pivot的都放在右边，小于pivot的都放在左边。如果pivot就在k的位置，直接返回，否则缩小范围继续上面的步骤
public class Solution {
public int findKthLargest(int[] nums, int k) {
if(nums == null || nums.length == 0) return Integer.MAX_VALUE;
//nums.length - k, the start position of last k
return find(nums, 0, nums.length-1, nums.length - k);
}
private int find(int[] nums, int start, int end, int k){
if(start>end) return Integer.MAX_VALUE;
int pivot = nums[end];
int left = start;
for(int i=start; i<end; i++){
if(nums[i]<=pivot){
swap(nums, left, i);
left++;
}
}
swap(nums, left, end);
if(left == k) return nums[left];//found
else if(left<k) return find(nums, left+1, end, k);
else return find(nums, start, left-1, k);
}
private void swap(int[] nums, int left, int right){
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
