Jos*_*son 3 algorithm data-structures
排序最多1000万个7位数字.约束:1M RAM,高速.几秒钟是好的.
[编辑:来自提问者的评论:输入值不同]
使用位图数据结构是解决此问题的好方法.
这意味着我需要一个字符串,长度最多为1000万???? RAM足够了吗？困惑在这里.谢谢
Jes*_*hen 10
因此,1MB中有~8,000,000位,但如果你使用位向量进行任意7位数(最多9,999,999),则排序将无效.同样,如果可以重复某些数字,它将无法工作,因为您只能将{0,1}存储在位向量中.
但是假设,(我认为你的问题在于)你有一个0到8,000,000之间的整数序列,没有重复,你可以简单地分配一个8,000,000位的归零数组,然后对于每个数字,勾选相应的位.阵列.然后输出排序列表只是按顺序读取该数组并输出每个1值的索引.
如果你问的是更复杂的问题版本(0到1000万,允许重复),那么你将需要对适合ram的块进行排序,将它们存储在磁盘上,然后你可以在线性时间内合并这些块.流(因此您不必将整个内容存储在内存中).这是python中非常类似的一个实现:http://neopythonic.blogspot.com/2008/10/sorting-million-32-bit-integers-in-2mb.html