题目
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.
答案
class Solution {
public void swap(int[] nums, int left, int right) {
int t = nums[left];
nums[left] = nums[right];
nums[right] = t;
}
public int partition(int[] nums, int left, int right, int k) {
int pivotIndex = k;
int pivot = nums[pivotIndex];
int cut = left;
swap(nums, pivotIndex, right);
for(int i = left; i < right; i++) {
if(nums[i] < pivot)
swap(nums, i, cut++);
}
swap(nums, right, cut);
return cut;
}
public int quickselect(int[] nums, int left, int right, int k) {
int pivotIndex = partition(nums, left, right, k);
if(pivotIndex == k)
return nums[k];
else if (k < pivotIndex)
return quickselect(nums, left, pivotIndex - 1, k);
else
return quickselect(nums, pivotIndex + 1, right, k);
}
public int findKthLargest(int[] nums, int k) {
return quickselect(nums, 0, nums.length - 1, nums.length - k);
}
}
