借组磁带机求第K小元素

如果输入在磁带机上， 你的机器只有一个磁带机驱动器和几十字的内存，如何找第K小的数 1. 遍历一遍磁带，随即选择一个数M 2. 再遍历一遍磁带， 计算大于和小于M的个数，这样就可以获得数M在总序列中的排名，这里考虑到可能有重复元素所以要统计大于和小于的个数 3. 如果M的排名正好为所求，则结束；否则如果M的排名大于K，则下次遍历磁带时随即选择一个小于M的数，统计它的排名；如果M的排名小于K，下次遍历磁带的时候随即选择一个大于M的数，统计排名 4. 经过步骤3，所选数的范围缩小，最后就能找到所要求的数 5. 最多遍历磁带2logN次， 每次遍历时间O(n),总时间复杂度为O(nlogn) 目前求第K小的数，比较好的算法时间复杂度为O(n),常数大概为3.4

转载于:https://www.cnblogs.com/qianye/archive/2012/11/24/2786367.html

总结

以上是生活随笔为你收集整理的借组磁带机求第K小元素的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。