想象以下场景：我有一个 10 Mb 的整数数组存储在只读存储介质上。我希望按升序打印数字。但是，我只有 2 Mb 的主内存（并且没有硬盘）。
一个非常简单的 O(n 2 ) 解决方案（不使用可用的主内存）将重复扫描整个输入数组并增量输出下一个最小整数。我尝试在谷歌上搜索更好的排序算法，但答案一直引导我使用就地或外部排序算法，由于只读存储限制，这将不起作用。有更好的解决方案吗？
问问题
261 次
1 回答
5
您可以使用主内存来减少扫描次数，并使用您提供的关系 o 大小，非常显着。
第一次扫描：在内存中存储一个几乎是主内存大小的内存，其中包含迄今为止发现的最小数字。当存储尚未满时，添加从数组中读取的下一个数字。店满时，比较店里最大的数字，如果新的小一点，就去掉最大的数字，再加上新的。扫描完整个数组后，按顺序输出找到的数字，记住存储的最大数字以及该块中出现的频率。
后续扫描：如果扫描的数量等于前一个块中的最大数量，并且它的出现次数小于前一次扫描的次数，则增加它的出现次数，但不要将它添加到存储中，如果它的出现次数更大大于或等于记住的计数将数字添加到存储中（如有必要，从存储中删除最大的数字）。如果扫描的数字大于前一次扫描的最大数字，但小于存储中的最大数字（或存储尚未满），则将其添加到存储中（必要时删除最大的数字）。扫描完成后，按顺序输出存储的数字，记住目前输出的最大数字，以及总共输出的数字（最大的数字可能和上一次扫描的数字相同，
我不确定商店的最佳数据结构是什么，但我认为堆是一个不错的选择（与最大的比较：O（1），替换：O（日志大小），输出的最终排序：O （大小*日志大小），几乎没有二叉搜索树的内存开销）。
于 2012-09-19T01:09:05.740 回答