在Java中高效地从大型数组中删除重复字符串？

Question

我正在考虑从一个（未排序的）字符串数组中删除重复项的最佳方法 - 这个数组包含数百万或数千万个字符串。该数组已经预先填充，因此优化目标仅在于删除重复项，而不是防止重复项最初填充！我考虑进行排序，然后进行二分查找以获得对数级别的搜索，而不是线性搜索。这将给我 nlogn + n 次搜索，虽然比未排序的(n^2)搜索好些，但仍然很慢。（也考虑过哈希等方式，但不确定吞吐量如何）。请帮忙！寻求一种既能解决速度问题又能解决内存问题的高效解决方案，因为涉及数百万个字符串，不能使用 Collections API！

- Preator Darmatheon

---

你为什么不想使用集合 API？ - Jon Skeet

现在，哈希似乎已经解决了所有关于大规模数据的时间和空间效率问题。如果他们不想让你使用集合API，我猜他们希望你自己描述一个哈希函数。 - Miserable Variable

Answer 1

在你的最后一句话之前，答案对我来说似乎很明显：如果需要保留顺序，请使用HashSet<String>或LinkedHashSet<String>：

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

如果您无法使用集合API，可以考虑构建自己的哈希集合......但在您给出不使用集合API的原因之前，很难给出更具体的答案，因为该原因可能会排除其他答案。

- Jon Skeet

---

好问题 - 这是我被问到的一个面试问题。我曾经提出过快速排序+相邻比较，但对方不满意。我相信他们是正确的 - 我希望在这里得到大家的意见，除了nlogn + n之外，有更好的方法吗？ - Preator Darmatheon

@PreatorDarmatheon：如果实现合理且冲突较低，构建一个哈希集可能是O(n)。但是请将上下文一同提供。 - Jon Skeet

我明白你的意思-如果实现策略有缺陷，你在建议什么陷阱? 有没有好的资源可用于构建这样的哈希集以解决我面临的标准问题? - Preator Darmatheon

@PreatorDarmatheon：如果你实现得不好，各种问题都可能会出现。如果我是你，我会在维基百科上查找哈希表。但是这些天你不太可能想要自己实际实现它-你会使用别人的实现。重要的是要知道这是正确的方法。 - Jon Skeet

@kasavbere：你为什么这么说？不使用集合API并不会阻止你使用哈希，只是停止你使用现有的哈希代码。 - Jon Skeet

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 *数组长度字节-则此解决方案似乎是最优的。

2. 如果空间是一个问题-那么快速排序+一次遍历。

3. 如果空间是一个大问题-实现一个带有实时去重的堆。 它仍然是O(n * log n)，但没有额外的空间。

- Eugene Retunsky

---

好的，除了堆的想法之外。"即时丢弃重复项"，真的吗？ - kasavbere

当堆建立完成后，从顶部取出最大值时，如果它与之前的最大值相等，则不要将其添加到结果数组中。 - Eugene Retunsky

Answer 3

我建议您在数组上使用修改后的归并排序。在合并步骤中，添加逻辑以删除重复值。这个解决方案具有n*log(n)的复杂度，如果需要，可以进行原地实现（在这种情况下，与普通归并排序相比，原地实现稍微困难一些，因为相邻的部分可能包含从已删除的重复项中移除的空隙，在合并时也需要关闭这些空隙）。

有关归并排序的更多信息，请参见http://en.wikipedia.org/wiki/Merge_sort。

- Michael Schmeißer

Answer 4

创建一个哈希集合来处理这个任务是非常昂贵的。事实上，他们告诉你不要使用集合API的整个原因就在于他们不想听到哈希这个词。所以只能遵循下面的代码。

请注意，你在对数组进行排序之后才提供了二分查找：这没有任何意义，这可能是你的建议被拒绝的原因。

选项1：

public static void removeDuplicates(String[] input){
    Arrays.sort(input);//Use mergesort/quicksort here: n log n
    for(int i=1; i<input.length; i++){
        if(input[i-1] == input[i])
            input[i-1]=null;
    }       
}

选项2：

public static String[] removeDuplicates(String[] input){
    Arrays.sort(input);//Use mergesort here: n log n
    int size = 1;
    for(int i=1; i<input.length; i++){
        if(input[i-1] != input[i])
            size++;
    }
    System.out.println(size);
    String output[] = new String[size];
    output[0]=input[0];
    int n=1;
    for(int i=1;i<input.length;i++)
        if(input[i-1]!=input[i])
            output[n++]=input[i];
    //final step: either return output or copy output into input; 
    //here I just return output
    return output;
}

选项3：（由949300添加，基于选项1）。请注意，这会破坏输入数组，如果不可接受，您必须制作副本。

public static String[] removeDuplicates(String[] input){
    Arrays.sort(input);//Use mergesort/quicksort here: n log n
    int outputLength = 0;
    for(int i=1; i<input.length; i++){
        // I think equals is safer, but are nulls allowed in the input???
        if(input[i-1].equals(input[i]))
            input[i-1]=null;
        else
           outputLength++;
    }  

    // check if there were zero duplicates
    if (outputLength == input.length)
       return input;

    String[] output = new String[outputLength];
    int idx = 0;
    for ( int i=1; i<input.length; i++) 
       if (input[i] != null)
          output[idx++] = input[i]; 

    return output;   
}

- kasavbere

---

我喜欢这种一般的方法，不过为了安全起见，我会使用equals()而不是==。请参考修改后的选项3。 - user949300

当然可以！我最初使用int[]编写它，因为这样更容易测试。我会进行编辑。 - kasavbere

请检查我的编辑后的选项3，它基于您的选项1/2，但只执行一次比较循环。 - user949300

一个加速的想法 - 基于字符串的哈希码进行快速排序，比实际的字符串要快得多。但是，比较相邻元素的循环则要复杂得多。 - user949300

@kasavbere：从O(n log n)的解法转换为O(n)的解法？当问题明确说明存在一个“大规模”的字符串集合时？对我来说，哈希似乎是相当合理的选择。 - Jon Skeet

Answer 5

嗨，你需要把它们放到一个数组里吗？使用哈希值（如集合）的集合会更快。因为每个值都有其唯一的哈希值。

如果你把所有条目放入一个集合类型的集合中，你可以使用

 HashSet(int initialCapacity) 

构造函数用于在运行时防止内存扩展。

  Set<T> mySet = new HashSet<T>(Arrays.asList(someArray))

如果内存不需要扩展，Arrays.asList()的运行时复杂度为O(n)。

- Jonny Schubert

Answer 6

由于这是一道面试题，我认为他们希望你自己来实现而不是使用set api。

你可以建立一个二叉树并创建一个空数组来存储结果，而不是先对其进行排序再进行比较。

数组中的第一个元素将是根节点。

1. 如果下一个元素等于该节点，则返回。->这会删除重复元素

2. 如果下一个元素小于该节点，则将其与左侧进行比较，否则将其与右侧进行比较。

重复以上两个步骤，直到到达树的末尾，然后您就可以创建一个新节点并知道这还没有重复。将此新节点值插入数组中。

遍历所有原始数组元素后，您将获得一个按原始顺序没有重复的新数组副本。

遍历需要O(n)时间，搜索二叉树需要O(logn)时间（插入应该只需要O(1)，因为您只需将其附加而不是重新分配/平衡树），因此总计应为O(nlogn)。

- evanwong

---

插入应该只需要O(1)的时间复杂度在哪个世界里？！我不会给这个点踩反对票。但是请考虑一下。 - kasavbere

是的，在二叉搜索树中，平均插入应该需要O(logn)时间。这个插入复杂度O(logn)实际上是因为它首先进行了搜索。我的建议是说搜索已经花费O(logn)的时间来找到正确的节点，所以实际插入只是将新节点连接到节点的左侧或右侧。这难道不仅是O(1)吗？ - evanwong

Answer 7

如果他们想要超级快的速度，让我们尽可能多地使用字符串的哈希码。

1. 循环遍历数组，获得每个字符串的哈希码，并将其添加到您喜欢的数据结构中。由于您不能使用 Collection，请使用 BitSet。注意，您需要两个，一个用于正数，一个用于负数，并且它们都非常庞大。

2. 再次循环遍历数组，使用另一个 BitSet。True 表示字符串通过。如果字符串的哈希码不存在于 Bitset 中，则可以将其标记为 true。否则，将其标记为可能重复项，即 false。顺便统计一下可能重复项的数量。

3. 将所有可能的重复项收集到一个名为 possibleDuplicates 的大型 String[] 中。将其排序。

4. 现在，在原始数组中遍历可能的重复项，并在 possibleDuplicates 中进行二进制搜索。如果存在，那么你还是被卡住了，因为你想要包含它一次，但不是所有其他时间。所以你需要另一个数组。有点混乱，我得去吃饭了，但这是一个开始...

- user949300