当前位置: 代码迷 >> 综合 >> C++复习之路:算法与数据结构相关 2:top(k)k个最值
  详细解决方案

C++复习之路:算法与数据结构相关 2:top(k)k个最值

热度:91   发布时间:2024-02-02 11:01:22.0

一般是求k个最大值、最小值的情况类似。

解法有很多:

1:直接全部排序(当数据量比较大的时候,最傻最耗费资源)

 

2.利用快排的思想:

 

先进行一趟快排,假设标记位置的下标为index,那么当index==k时index左边的为前k个数,只需对这k个数排序即可;

如果index>K,那么第k个大小的值在index的左边,算法对index左边再次快排;

如果index<K,那么第k个大小的值在index的右边,算法对index左边再次快排;

直到index==k找到第k个大小的值,然后对其左边排序。

虽然有所优化,但是还是很耗费资源。

 

3.利用堆排序,这个算是比较优化的方法,时间复杂度也比较小O(nlogn) (这部分的代码待补充,先挖个坑)

这是一种局部淘汰法。先读取前K个数,建立一个最小堆。然后将剩余的所有数字依次与最小堆的堆顶进行比较,如果小于或等于堆顶数据,则继续比较下一个;否则,删除堆顶元素,并将新数据插入堆中,重新调整最小堆。当遍历完全部数据后,最小堆中的数据即为最大的K个数。 

 

4.分治法:如果数据量很大,可以考虑分成n份,先找出每份中前k个最值,再把N*k个数据放入内存,如果N*k还是很大就继续把n*k分为m份,找出每份中前k个最值,再把m*k个数据放入内存,以此类推,直到能放入内存,再使用上面的方法。