有效地从java中的大型数组中删除重复的字符串？

Question

我正在考虑从(未排序的)字符串数组中删除重复项的最佳方法 - 该数组包含数百万或数千万字符串.数组已经预先填充,因此优化目标只是删除重复而不是防止重复从最初填充!!

我正在考虑进行排序然后二元搜索以获得log(n)搜索而不是n(线性)搜索.这将给我nlogn + n次搜索,这些搜索除了未排序(n ^ 2)之外的搜索效果更好,但这似乎仍然很慢.(还考虑了散列但不确定吞吐量)

请帮忙!寻找一种解决速度和内存的高效解决方案,因为在不使用Collections API的情况下涉及数百万字符串!

Answer 1

直到你的最后一句话,答案对我来说似乎很明显:如果你需要保留顺序,请使用a HashSet<String>或a LinkedHashSet<String>:

HashSet<String> distinctStrings = new HashSet<String>(Arrays.asList(array));

如果不能使用集合API,可以考虑建立自己的哈希集合......但直到你给一个理由,为什么你不希望使用集合API,很难给出更具体的答案,因为这原因也可以排除其他答案.

Answer 2

分析

让我们进行一些分析:

1. 使用HashSet.时间复杂度 - O(n).空间复杂度O(n).注意,它需要大约8*个数组大小的字节(8-16个字节 - 对新对象的引用).

2. 快速排序.时间 - O(n*log n).空间O(log n)(最坏的情况是O(n*n)和O(n)).

3. 合并排序(二叉树/ TreeSet).时间 - O(n*log n).空间O(n)

4. 堆排序.时间O(n*log n).空间O(1).(但它比2和3慢).

在堆排序的情况下,您可以在飞行中远离重复,因此您将在排序后保存最终传递.

结论

1. 如果您关心时间,并且不介意为HashSet分配8*array.length个字节 - 这个解决方案似乎是最佳的.

2. 如果空间是一个问题 - 然后QuickSort +一次通过.

3. 如果空间是一个大问题 - 实施一个堆飞行丢弃重复.它仍然是O(n*log n)但没有额外的空间.