我想编写一个函数，该函数采用整数集合并从集合中删除重复项。我不能应用任何排序算法。同样，我不能复制该集合。我需要节省内存并提供一个高效的解决方案，可以处理数百万个项目而不会显着过度使用电池。
问问题
178 次
1 回答
1
如果您的内存非常不足，最好的解决方案是首先不在列表中包含冗余整数。为此，您可以使用一个布尔数组 [0..65536]（您可以将其“打包”8 x 8 以使其更小），该数组记录已使用的数组。
另一种解决方案是通过在正确的位置插入项目来对列表进行排序，但如果它们已经在这里，则不要插入它们。插入将在每个项目的日志中（到目前为止的唯一项目数），因此它应该是您列表的 *log(n) 时间。
如果您无法控制源，您仍然可以使用布尔数组，如果需要，可能更大，然后初始化它（将所有设置为 false，然后：isUsed[itemList[i]] = true;），然后您可以处理列表，以便再次拥有内存，然后从数组中构建一个新列表。所以输出将被排序。
如果您的整数是 32 位，则数组将是 500 MB 大，所以可能太大了...，但取决于整数分布（是否有广泛的可能数字？？），您可能确实能够降低该大小...
请注意，如果您的内存非常不足，您可能会使用对象池来重用对象。
（您甚至可以重新使用刚刚从列表中删除的对象。）
于 2012-12-29T18:41:09.543 回答