Top K 问题
程序员文章站
2024-03-15 22:05:12
...
基于堆排序(内存足够存放所有数据)
堆排序的初始建堆操作时间复杂度为O(N)(可证,通过级数),之后每加入新元素或者取走堆顶元素的时间复杂度为O(logN),所以堆排序的时间复杂度为O (N*logN) 。
因为每次取堆顶的元素都是最大/最小的,这里建大顶堆的话,取到第K大的元素时间复杂度为O(N+K*logN) 。
class Solution{
public:
void AdjustHeap(vector<int>& nums, int i, int n){
// nums[0] 是堆顶,堆*有n个元素,现在调整 i
int root = i, j = root * 2 + 1;
while(j < n){
if(j + 1 < n && nums[j + 1] > nums[j]) // 对比左右子节点的大小
j++;
if(nums[root] < nums[j]){
swap(nums[root], nums[j]);
root = j;
j = root * 2 + 1;
}
else
break;
}
}
int findKthLargest(vector<int>& nums, int k){
if(k > nums.size())
return 0;
// 初始化大顶堆
for(int i = nums.size() / 2 - 1; i >= 0; --i) // 从 n/2-1 开始
AdjustHeap(nums, i, nums.size());
// 对k-1个元素出堆
for(int i = 0; i < k - 1; ++i){
nums[0] = nums[nums.size() - 1 - i]; // 把堆中最后一个元素移到堆顶
AdjustHeap(nums, 0, nums.size() - i);
}
return nums[0];
}
};
基于堆排序(内存不足够存放数据)(不修改原数组)
当数据量特别大,以至于内存中装不下,只能装入硬盘的时候。或者要求不修改原数组时。
这时可以先取K个元素,建一个K个元素的小顶堆,之后每取一个元素就与堆顶的元素对比,小的话就扔掉,大的话就把堆顶元素出堆,把新元素入堆,保证目前遍历的所有元素中前K大的元素都在堆中。遍历结束后,堆顶的元素就是第K大的元素。
这个算法的时间复杂度为O(N*logK)。
// Top K
#include <iostream>
#include <fstream>
using namespace std;
class Solution{
public:
void AdjustHeap(int *heap, int i, int n){ // 小顶堆
// nums[0] 是堆顶,堆*有n个元素,现在调整 i
int root = i, j = root * 2 + 1;
while(j < n){
if(j + 1 < n && heap[j + 1] < heap[j]) // 对比左右子节点的大小
j++;
if(heap[root] > heap[j]){
swap(heap[root], heap[j]);
root = j;
j = root * 2 + 1;
}
else
break;
}
}
void PrintTopK(ifstream &in, int k) {
if (k <= 0 || !in.is_open()) {
printf("文件打开错误或K<=0\n");
return;
}
int *heap = new int[k];
int num;
for (int i = 0; i < k; ++i) {
if (in >> num)
heap[i] = num;
else {
printf("数字不足%d个\n", k);
return;
}
}
for(int i = k / 2 - 1; i >= 0; --i) // 初始化小顶堆
AdjustHeap(heap, i, k);
while (in >> num) {
if (num > heap[0]) {
heap[0] = num;
AdjustHeap(heap, 0, k);
}
}
for (int i = 0; i < k; ++i)
printf("%d\n", heap[i]);
}
};
int main() {
ifstream in;
Solution s;
in.open("number.txt", ios::in);
s.PrintTopK(in, 10);
in.close();
return 0;
}