题目
- 215. 数组中的第K个最大元素
- 剑指 Offer II 059. 数据流的第 K 大数值
思路一
- 快速排序的partition结合减治法查找元素。
- 一趟快速排序(partition),可以将该次排序的元素pivot放到排序后的数组的最终位置,因此找第K大的元素,也就是查找排序后的数组的倒数第k个位置的元素。
- 每次partition都返回此次排序的位置,因此可以采用减治法判断此次排序的位置是不是倒数第k个位置。
class Solution {
public int findKthLargest(int[] nums, int k) {
shuffle(nums); // 洗牌算法,打乱数组元素顺序
int low = 0, high = nums.length - 1;
// 利用快排,将查找第k个最大元素转化为查找num.length - k个位置
int res = nums.length - k;
while(low <= high){ // 在[low, high]中查找res
int p = partition(nums, low, high);
if(p == res){
return nums[p];
} else if(p < res){
low = p + 1;
} else{
high = p - 1;
}
}
return -1;
}
private int partition(int[] nums, int low, int high){
int pivot = nums[low];
int i = low + 1, j = high;
while(i <= j){
while(i < high && nums[i] <= pivot)
++i;
while(j > low && nums[j] > pivot)
--j;
if(i >= j)
break;
swap(nums, i, j);
}
swap(nums, low, j);
return j;
}
private void shuffle(int[] nums){
int n = nums.length;
Random rand = new Random();
for(int i = 0; i < n; ++i){
int r = i + rand.nextInt(n - i);
swap(nums, i, r);
}
}
private void swap(int[] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
思路2
- 采用小顶堆。
- 维护一个大小为k的小顶堆,堆中堆顶之外的k-1个元素都比堆顶元素大,则堆顶元素就是第k大。
class Solution {
public int findKthLargest(int[] nums, int k) {
// 维护一个大小为k的小顶堆
PriorityQueue minHeap = new PriorityQueue<>(k);
for(int i = 0; i < k; ++i){
minHeap.offer(nums[i]);
}
for(int i = k; i < nums.length; ++i){
if(nums[i] > minHeap.peek()){ // 大于堆顶元素,则堆顶元素不是第k大
minHeap.poll();
minHeap.offer(nums[i]);
}
}
return minHeap.peek();
}
}