5

我正在考虑从（未排序的）字符串数组中删除重复项的最佳方法 - 该数组包含数百万或数百万个 stringz ..该数组已预先填充，因此优化目标仅在于删除重复而不是防止重复从最初填充！！

我正在考虑进行排序然后进行二进制搜索以获得对数（n）搜索而不是n（线性）搜索。这会给我 nlogn + n 个搜索，其中 althout 比未排序的 (n^2) 搜索更好 = 但这似乎仍然很慢。（也在考虑散列，但不确定吞吐量）

请帮忙！由于涉及数百万个字符串而不使用 Collections API，因此正在寻找一种既能解决速度又能解决内存问题的有效解决方案！

4

7 回答 7

7

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

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

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

于 2012-04-06T15:31:59.247 回答
5

分析

让我们进行一些分析：

  1. 使用哈希集。时间复杂度 - 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. 如果空间是一个问题 - 然后快速排序 + 一次通过。

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

于 2012-04-06T16:18:39.777 回答
2

我建议您在数组上使用修改后的合并排序。在合并步骤中，添加逻辑以删除重复值。此解决方案具有 n*log(n) 复杂性，并且可以在需要时就地执行（在这种情况下，就地实现比普通合并排序更难，因为相邻部分可能包含来自已删除重复项的间隙，这也需要合并时关闭）。

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

于 2012-04-06T15:42:28.970 回答
1

创建一个哈希集来处理这个任务太昂贵了。显然，事实上他们告诉你不要使用 Collections 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;   
}
于 2012-04-06T23:13:09.600 回答
0

嗨，您需要将它们放入数组中。使用像集合这样的哈希值的集合会更快。这里每个值都是唯一的，因为它的哈希值。

如果将所有条目都放入一个集合类型。您可以使用

 HashSet(int initialCapacity)

构造函数来防止运行时内存扩展。

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

如果不必扩展内存，则 Arrays.asList() 的运行时间为 O(n)。

于 2012-04-06T15:34:37.717 回答
0

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

  1. 遍历数组，获取每个字符串的哈希码，并将其添加到您喜欢的数据结构中。由于不允许使用 Collection，因此请使用 BitSet。请注意，您需要两个，一个用于正面，一个用于负面，它们每个都很大。

  2. 使用另一个 BitSet 再次循环遍历数组。True 表示字符串通过。如果 Bitset 中不存在 String 的哈希码，您可以将其标记为 true。否则，将其标记为可能重复，为假。当你在做的时候，计算有多少可能的重复。

  3. 将所有可能的重复项收集到一个名为 possibleDuplicates 的大字符串 [] 中。解决。

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

于 2012-04-07T00:01:15.073 回答
0

由于这是一个面试问题，我认为他们希望您提出自己的实现而不是使用 set api。

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

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

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

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

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

在遍历原始数组的所有元素后，您会得到一个数组的新副本，并且在原始顺序中没有重复。

遍历需要 O(n) 并且搜索二叉树需要 O(logn) （插入应该只需要 O(1) 因为你只是附加它而不是重新分配/平衡树）所以总数应该是 O(nlogn) .

于 2012-04-06T16:11:42.813 回答