文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

堆排序怎么解决TopK问题

2024-04-02 19:55

关注

本篇内容主要讲解“堆排序怎么解决TopK问题”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“堆排序怎么解决TopK问题”吧!

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:  输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 示例 2:  输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4

经典的TopK问题还有:最大(小) K 个数、前 K 个高频元素、第 K 个最大(小)元素

对此TopK问题本质上是一个排序问题,排序算法一共有十个,这个还有很多排序算法没有介绍过。

堆排序怎么解决TopK问题

至于为什么TopK问题最佳的答案是堆排序?其实在空间和时间的复杂度来考量,虽说快排是最好的排序算法,但是对于100亿个元素从大到小排序,然后输出前 K  个元素值。

可是,无论我们掌握的是快速排序算法还是堆排序算法,在排序的时候,都需要将全部的元素读入到内存中。也就是说,100亿个整型元素大约需要占用40GB的内存空间,这听起来就不像是普通民用电脑能干的事情,(一般的民用电脑内存比这个小,比如我写文章用的电脑内存是  32GB)。

众所周知,快速排序和堆排序的时间复杂度都可以达到,但是对于快速排序来说,数据是顺序访问的。而对于堆排序来说,数据是跳着访问的。比如堆排序中,最重要的一个操作就是数据的堆化。因此,快速排序的时间复杂度是优于堆排序的。

但是快速排序是新建数组,空间复杂度是,远低于堆排序的。对于庞大的数据量,应该优先选择堆排序。

如果使用heapq内置模块,寻找数组中的第K个最大元素就是一行代码,heapq中的nlargest接口封装好了,返回的是一个数组,需要切片取值。

import heapq class Solution:     def findKthLargest(self, nums: List[int], k: int) -> int:         return heapq.nlargest(k,nums)[-1]

当然,一般都是手写堆排序,寻找数组中的第K个最大元素建立最小堆,寻找数组中的第K个最小元素建立最大堆,

思路:「取nums前K个元素建立大小为K的最小堆,后面就是维护一个容量为k的小顶堆,堆中的k个节点代表着当前最大的k个元素,而堆顶显然是这k个元素中的最小值。」

因此只要遍历整个数组,当二叉堆大小等于K后,当遇见大于堆顶数值的元素时弹出堆顶,并压入该元素,持续维护最大的K个元素。遍历结束后,堆顶元素即为第K个最大元素。时间复杂度。

class Solution:     def findKthLargest(self, nums: List[int], k: int) -> int:         heapsize=len(nums)         def maxheap(a,i,length):             l=2*i+1             r=2*i+2             large=i             if l<length and a[l]>a[large]:                 large=l             if r<length and a[r]>a[large]:                 large=r             if large!=i:                 a[large],a[i]=a[i],a[large]                 maxheap(a,large,length)                      def buildheap(a,length):             for i in range(heapsize//2,-1,-1):                 maxheap(a,i,length)          buildheap(nums,heapsize)         for i in range(heapsize-1,heapsize-k,-1):             nums[0],nums[i]=nums[i],nums[0]             heapsize-=1             maxheap(nums,0,heapsize)         return nums[0]

相反如果是求前k个最小,那么就用最大堆,因此面对TopK问题,最完美的解法是堆排序。因此,只有你看到数组的第K个&hellip;&hellip;,马上就是想到堆排序。

如果在数据规模小、对时间复杂度、空间复杂度要求不高的时候,真没必要上 “高大上” 的算法,写一个快排就很完美了。

TopK问题就像搜索引擎每天会接收大量的用户搜索请求,它会把这些用户输入的搜索关键词记录下来,然后再离线地统计分析,得到最热门的Top10搜索关键词,啥啥惹事就出来了。

到此,相信大家对“堆排序怎么解决TopK问题”有了更深的了解,不妨来实际操作一番吧!这里是编程网网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-前端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯