概述
找出第k大的数字
利用快速排序的思想，从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中元素小于X。这时有两种情况：
1. Sa中元素的个数小于k，则Sb中的第k-|Sa|个元素即为第k大数；
2. Sa中元素的个数大于等于k，则返回Sa中的第k大数。时间复杂度近似为O(n)
找出前K大数:
思路：快速排序。主要思想是找一个“轴”节点，将数列交换变成两部分，一部分全都小于等于“轴”，另一部分全都大于等于“轴”，然后对两部分 递归处理。其平均时间复杂度是O（NlogN）。从中可以受到启发，如果我们选择的轴使得交换完的“较大”那一部分的数的个数j正好是n，不也就完成了在 N个数中寻找n个最大的数的任务吗？当然，轴也许不能选得这么恰好。可以这么分析，如果j>n，则最大的n个数肯定在这j个数中，则问题变成在这j 个数中找出n个最大的数；否则如果j<n，则这j个数肯定是n个最大的数的一部分，而剩下的j-n个数在小于等于轴的那一部分中，同样可递归处理。
这个算法的平均复杂度是O（N）的。
转自http://blog.sina.com.cn/s/blog_5b101dbf0100o82b.html
最后
以上就是飞快草丛为你收集整理的N个整数寻找k个最小的数的全部内容，希望文章能够帮你解决N个整数寻找k个最小的数所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复