输入:

一个最多包含n个正整数的文件,每个数都小于n,其中n=107。如果在输入文件中有任何整数重复出现就是致命错误,没有其他数据与该数据相关联。

输出:

按升序排列的输入整数的列表。

约束:

最多有1MB的内存空间可用,有充足的磁盘存储空间可用,运行时间最多几分钟,10秒就不需要进一步优化了。

  • 是否能用大约800万个可用位,表示最多1000万个互异的整数?

条件:

输入文件中的所有整数都可以在1MB内存中表示。

思路:

用位图或位向量表示集合

用一个20位长的字符串表示一个所有元素都小于20的简单非负整数集合

{1,2,3,5,8,13}表示为:

01110100100001000000(一个20位的数组,下标从0到19)

问题演变为:

使用一个具有1000万个位的字符串来表示这个文件,其中,当且仅当整数i在文件中存在时,第i位为1。

特有属性:

  1. 输入数据限制在相对较小的范围内
  2. 数据没有重复
  3. 对于每条记录而言,除了单一整数外,没有任何其他关联数据

执行步骤:

  1. 初始化集合,将所有位都置为0
  2. 读入文件中的整数,将对应位都置为1
  3. 检验每一位,如果该位为1,就输出对应位的数组下标

results matching ""

    No results matching ""