我来帮你实现这个寻找前100个最大数据的算法。这个算法的时间复杂度是O(n log 100)，空间复杂度是O(100)。
C++实现
#include<iostream>#include<vector>#include<queue>#include<functional>#include<random>usingnamespacestd;// 寻找前k个最大元素的算法vector<int>findTopK(constvector<int>&nums,intk){if(nums.size()<=k){vector<int>result(nums.begin(),nums.end());returnresult;}// 创建最小堆priority_queue<int,vector<int>,greater<int>>minHeap;// 步骤1: 插入前k个元素for(inti=0;i<k;i++){minHeap.push(nums[i]);}// 步骤2-3: 遍历剩余元素，维护堆for(size_t i=k;i<nums.size();i++){if(nums[i]>minHeap.top()){minHeap.pop();// 弹出堆顶minHeap.push(nums[i]);// 插入当前元素}}// 步骤4: 堆中元素即为前k个最大数据vector<int>result;while(!minHeap.empty()){result.push_back(minHeap.top());minHeap.pop();}returnresult;}intmain(){// 生成测试数据vector<int>data(1000);random_device rd;mt19937gen(rd());uniform_int_distribution<>dis(1,10000);for(inti=0;i<1000;i++){data[i]=dis(gen);}intk=100;vector<int>topK=findTopK(data,k);cout<<"前"<<k<<"个最大元素："<<endl;for(size_t i=0;i<topK.size();i++){cout<<topK[i]<<" ";if((i+1)%10==0)cout<<endl;}cout<<endl;return0;}Python实现
importheapqimportrandomfromtypingimportListdeffind_top_k(nums:List[int],k:int)->List[int]:""" 寻找前k个最大元素的算法 实现步骤： 1. 创建一个最小堆并将前k个数据插入堆中 2. 遍历剩余的数据，如果当前数据比堆顶大，就替换堆顶元素 3. 继续遍历所有数据，确保堆中保留的是最大的k个数据 4. 遍历完成后，堆中的元素就是前k个最大的数据 """iflen(nums)<=k:returnsorted(nums,reverse=True)# 步骤1: 创建最小堆并插入前k个元素min_heap=nums[:k]heapq.heapify(min_heap)# 建立最小堆# 步骤2-3: 遍历剩余元素，维护堆fornuminnums[k:]:ifnum>min_heap[0]:# 如果当前元素比堆顶大# 弹出堆顶，插入当前元素heapq.heapreplace(min_heap,num)# 步骤4: 堆中元素即为前k个最大数据# 堆是最小堆，需要排序后返回result=sorted(min_heap,reverse=True)returnresultdeffind_top_k_alternative(nums:List[int],k:int)->List[int]:"""另一种实现方式，更清晰地体现算法步骤"""iflen(nums)<=k:returnsorted(nums,reverse=True)# 步骤1: 创建最小堆并插入前k个元素min_heap=[]foriinrange(k):heapq.heappush(min_heap,nums[i])# 步骤2-3: 遍历剩余数据foriinrange(k,len(nums)):ifnums[i]>min_heap[0]:# 比堆顶大# 我就往堆里面插heapq.heappop(min_heap)# 弹出堆顶heapq.heappush(min_heap,nums[i])# 插入当前数据# 步骤4: 返回结果returnsorted(min_heap,reverse=True)defmain():# 生成测试数据random.seed(42)data=[random.randint(1,10000)for_inrange(1000)]k=100# 使用方法1top_k=find_top_k(data,k)print(f"前{k}个最大元素：")fori,numinenumerate(top_k,1):print(f"{num:6d}",end=" ")ifi%10==0:print()print()# 验证结果正确性sorted_data=sorted(data,reverse=True)[:k]print(f"算法结果是否正确:{top_k==sorted_data}")# 使用方法2top_k2=find_top_k_alternative(data,k)print(f"方法2结果是否正确:{sorted(top_k2)==sorted(top_k)}")if__name__=="__main__":main()算法复杂度分析
- 时间复杂度: O(n log k)，其中n是总数据量，k=100
- 空间复杂度: O(k)，只需要维护大小为100的堆
关键点说明
- 使用最小堆的原因：我们想要最大的k个元素，使用最小堆可以让我们在O(1)时间内知道当前堆中最小的元素
- 堆顶的作用：堆顶始终是当前堆中最小的元素，也就是第k大的候选者
- 替换条件：只有当新元素大于堆顶时，才进行替换，确保堆中始终是见过的最大的k个元素
- “我就往堆里面插”：这个操作在代码中体现为
"heapq.heapreplace()"或先pop再push的操作
两种实现方式都可以，Python版本提供了两种写法：
“find_top_k”：使用
“heapq.heapreplace()”，更简洁
“find_top_k_alternative”：分步操作，更清晰地体现算法步骤
