使用 Java 从大型整数数组中删除重复项

arrays loops integer java

2022-09-04 23:59:10

您知道使用Java从非常大的整数数组中删除重复值的任何时间有效的方法吗？数组的大小取决于登录的用户，但始终超过 1500000 个未排序的值，并带有一些重复项。每个整数都包含一个介于 100000 和 9999999 之间的数字。

我尝试将其转换为列表，但我服务器上的堆不允许此数据量（我的ISP已限制它）。for 循环中的常规 for 循环需要 5 分钟以上的时间来计算。

没有重复项的数组的大小是我将存储在数据库中的大小。

帮助将不胜感激！

答案 1

你也许可以使用一个位设置？我不知道Java的BitSet有多高效。但是9999999可能的值只需要9999999 / 8 = 1250000字节 = 略高于1Mb。在遍历值数组时，将相应的位设置为 true。然后，您可以遍历位集，并在找到设置为 true 的位时输出相应的值。

1Mb将适合CPU缓存，因此根据位集实现，这可能非常有效。

这也具有对数据进行排序的副作用。

和。。。这是一个O（n）算法，因为它需要对输入数据进行单次传递，集合操作是O（1）（对于像这样的基于数组的集合），输出传递也是O（m），其中m是唯一值的数量，并且根据定义，必须<= n。

答案 2

在开始向列表中添加项目之前，我会创建一个哈希集，在其中存储列表中包含的所有值。然后只需检查，以确保哈希集不包含要添加的值。