c# - 在不使用临时内存的情况下从列表中删除重复项

Question

我想编写一个函数，它接受一个整数集合并从集合中删除重复项。我不能应用任何排序算法。同样，我无法复制该集合。我需要节省内存并提供一种高效的解决方案，可以处理数百万件元素而不会显着过度使用电池。

Answer 1

如果你的内存很短，最好的解决办法是不包括多余的列表中的整数排在首位。为此，您可以使用 bool 数组 [0..65536](您可以将 8 乘 8 ‘打包’以使其更小)，它记录了哪一个已被使用。

另一种解决方案是对列表进行排序，方法是在正确的位置插入项目，但如果它们已在此处准备就绪，则不插入它们。插入将记录在每个项目的日志中(到目前为止唯一项目的数量)，因此对于您的列表来说，它应该类似于 n*log(n) 时间。

如果您无法控制源，您仍然可以使用 bool 数组，如果需要的话可以更大，然后初始化它(将所有设置为 false，然后:isUsed[itemList[i]] = true; )，然后您可以处理列表以便再次拥有内存，然后从数组中构建一个新列表。所以输出是有序的。
如果你的整数是 32 位，数组将是 500 MB 大，所以可能太大了......，但是取决于整数分布(是否有广泛的可能数字？？)，你可能确实能够降低那个尺寸......

请注意，如果内存不足，您可以使用对象池来重用对象。
(您甚至可以重新使用刚刚从列表中删除的对象。)