您知道使用 Java 从非常大的整数数组中删除重复值的任何省时的方法吗?数组的大小取决于登录用户,但总是会超过 1500000 个未排序的值和一些重复值。每个整数都包含一个介于 100000 和 9999999 之间的数字。
我尝试将其转换为列表,但我服务器上的堆不允许这个数据量(我的 ISP 对其进行了限制)。而一个 for 循环中的常规 for 循环需要超过 5 分钟的时间来计算。
没有重复的数组的大小是我将存储在我的数据库中的数组。
帮助将不胜感激!
最佳答案
您或许可以使用位设置?不知道Java的BitSet效率如何。但是 9999999 个可能的值只需要 9999999/8 = 1250000 字节 = 刚刚超过 1Mb。当您遍历值数组时,将相应的位设置为 true。然后你可以遍历这个位集,只要发现一个位设置为真,就输出相应的值。
1Mb 将适合 CPU 缓存,因此这可能非常有效,具体取决于位集实现。
这也有对数据进行排序的副作用。
并且...这是一个 O(n) 算法,因为它需要单次传递输入数据,集合操作是 O(1)(对于像这样的基于数组的集合),输出传递是也是 O(m),其中 m 是唯一值的数量,根据定义,必须 <= n。
关于java - 使用 Java 从大型整数数组中删除重复项,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3667543/