面试题精选:寻找最大的K个数

举报
xindoo 发表于 2022/04/16 02:33:15 2022/04/16
【摘要】 给你n个数,让你找出其中最大的K个数。 解法1: 很多人上来就对其进行排序,选用不同的排序方法有不同的时间复杂度,这里我们假设使用了最快的快排,时间复杂度为O(n*logn)。通过排序我摘出前K大的数。 但也许快排不是最优的,我们只找最大的K个数,何必要对所有的数进行排序,我们只需要进行局部排序即可,时间复杂度大概是O(N*K)...


给你n个数,让你找出其中最大的K个数。

解法1:

很多人上来就对其进行排序,选用不同的排序方法有不同的时间复杂度,这里我们假设使用了最快的快排,时间复杂度为O(n*logn)。通过排序我摘出前K大的数。

但也许快排不是最优的,我们只找最大的K个数,何必要对所有的数进行排序,我们只需要进行局部排序即可,时间复杂度大概是O(N*K)。

但快排和局部排序谁优谁劣是并不是一定的,当K大于某个数值时快排的优势就显现出来了,大概是logn吧。

解法2:

这个方法是基于快排的,但不是完整的快排。

回忆一下快排,在每一步中,都是将带排数据分成两部分,其中一部分中的任何一个都比另一部分中的任何都大,然后递归排序。

在这里,我们只要在递归过程中选包含最大的K个数的部分进行完整的快排,而对于其他的部分只进行快排的一部分。
    关于使用快排求第K大数的方法参见其他博文。在这个基础上,只需要做小小的改进就可以完成寻找最大K个数的功能了,时间复杂度O(N)。

解法3:

     以上的两个方法都需要对所有数据遍历多次,如果数据量太大,都没办法全部装进内存了,这时候我们何谈排序。

     其实我们有更优的解决方法,我们可以先拿出K个元素建一个最小堆,然后遍历其他元素,与堆顶的元素进行比较。

有三种情况:

   1  与堆顶元素相同,跳过。

   2  小于堆顶元素,跳过。根据最大堆性质,堆顶是堆中最小的元素,既然都比最小的都小,  肯定不属于最大的K个元素了。

   3  大于堆顶元素, 将其与堆顶元素对换, 然后维护这个堆。

结果遍历所有元素后,我们都得到保存最大K个数的堆,也就到达了我们的目的。

 

文章来源: xindoo.blog.csdn.net,作者:xindoo,版权归原作者所有,如需转载,请联系作者。

原文链接:xindoo.blog.csdn.net/article/details/9132853

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。