数组中的第K个最大元素
核心:快速排序,扩展只排多少个。
java
public int findKthLargest(int[] nums, int k) {
if (nums.length < 1 || k < 1 || k > nums.length) {
return -1;
}
return partition(nums, 0, nums.length - 1, nums.length - k);
}
public int partition(int[] nums, int start, int end, int k) {
if (start >= end) {
return nums[k];
}
int left = start;
int right = end;
int pivot = nums[(right - start) / 2 + start];
while (left <= right) {
while (left <= right && nums[left] < pivot) {
left++;
}
while (left <= right && nums[right] > pivot) {
right--;
}
if (left <= right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
if (k >= left) {
return partition(nums, left, end, k);
}
if (k <= right) {
return partition(nums, start, right, k);
}
return nums[k];
}
go
func findKthLargest(nums []int, k int) int {
if len(nums) < 1 || k < 1 || k > len(nums) {
return -1
}
return partition(nums, 0, len(nums)-1, len(nums)-k)
}
func partition(nums []int, start, end, k int) int {
if start >= end {
return nums[k]
}
pivot := nums[(end-start)/2+start]
left, right := start, end
for left <= right {
for left <= right && nums[left] < pivot {
left++
}
for left <= right && nums[right] > pivot {
right--
}
if left <= right {
nums[left], nums[right] = nums[right], nums[left]
left++
right--
}
}
if k >= left {
return partition(nums, left, end, k)
}
if k <= right {
return partition(nums, start, right, k)
}
return nums[k]
}