Leetcode | Top K系列

Top K问题

题名 难度 题解
215. 数组中的第K个最大元素 中等
347. 前K个高频元素 中等
973. 最接近原点的 K 个点 中等
703.数据流中的第 K 大元素 简单
658. 找到 K 个最接近的元素 中等
451. 根据字符出现频率排序 中等

215. 数组中的第K个最大元素

题目:
https://leetcode-cn.com/problems/kth-largest-element-in-an-array/

思路:

  1. 建立最大堆
  2. 交换堆尾元素与堆顶元素,此时堆尾是最大值,然后heapsize-1,相当于删除最大值,然后重新调整为最大堆
  3. 重复k-1次步骤2 ,堆顶元素nums[0]即为第k大的数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
void maxHeapify(vector<int>& a,int i,int heapsize){
int l = i*2+1;
int r = i*2+2;
int largest = i;
if(l<heapsize && a[l]>a[largest]){
largest = l;
}
if(r<heapsize && a[r]>a[largest]){
largest = r;
}
if(largest!=i){
swap(a[largest],a[i]);
maxHeapify(a,largest,heapsize);
}
}
void build(vector<int>& a,int heapsize){
for(int i = heapsize/2;i>=0;--i){
maxHeapify(a,i,heapsize);
}
}
int findKthLargest(vector<int>& nums, int k) {
int heapsize = nums.size();
build(nums,heapsize);
for(int i = nums.size()-1;i>=nums.size()-k+1;--i){
swap(nums[0],nums[i]);
heapsize--;
maxHeapify(nums,0,heapsize);
}
return nums[0];
}
};
分享到