Kth Largest Element 5
Question
Find K-th largest element in an array.
Notice
You can swap elements in the array
Example
In array [9,3,2,4,8], the 3rd largest element is 4.
In array [1,2,3,4,5], the 1st largest element is 5, 2nd largest element is 4, 3rd largest element is 3 and etc.
Challenge
O(n) time, O(1) extra memory.
Solution
用quick sort来解,平均时间复杂度为O(n)。
初始为求数组中从头到尾第nums.length - k + 1个元素(即从后往前第k个元素,即第k最大元素,)
然后用quick sort并返回分割点的index
如果该分割点正好是第nums.length - k + 1个元素,则找到并返回;否则若该分割点比k小,则递归地在数组index+1-数组尾区间寻找,若该分割点比k大,则递归地在数组头-index-1区间寻找
代码如下:
class Solution {
/*
* @param k : description of k
* @param nums : array of nums
* @return: description of return
*/
public int kthLargestElement(int k, int[] nums) {
// write your code here
if(nums == null || nums.length == 0 || k < 1 || k > nums.length){
return -1;
}
//第k大就是从小到大排第nums.length - k + 1大
return kthLargestHelper(nums, 0, nums.length - 1, nums.length - k + 1);
}
//quick sort模板
private int kthLargestHelper(int[] nums, int l, int r, int k){
if(l == r){
return nums[l];
}
int position = partition(nums, l, r);
if(position + 1 == k){
return nums[position];
}else if(position + 1 > k){
return kthLargestHelper(nums, l, position - 1, k);
}else{
return kthLargestHelper(nums, position + 1, r, k);
}
}
private int partition(int[] nums, int l, int r){
int start = l;
int end = r;
int pivot = nums[end];
while(start < end){
while(start < end && nums[start] <= pivot){
start++;
}
nums[end] = nums[start];
while(start < end && nums[end] > pivot){
end--;
}
nums[start] = nums[end];
}
nums[start] = pivot;
return start;
}
};