如何在不使用SET的情况下有效地从数组中删除重复项

Question

如何在不使用SET的情况下有效地从数组中删除重复项我被要求编写自己的实现来删除数组中的重复值。这是我所创造的。但是在测试了1，000，000个元素之后，它花了很长时间才完成。我能做些什么来改进我的算法，或者删除任何bug吗？我需要写我自己的实现，而不是使用Set, HashSet等等。或任何其他工具，例如迭代器。只是一个删除重复项的数组。public static int[] removeDuplicates(int[] arr) {     int end = arr.length;     for (int i = 0; i < end; i++) {         for (int j = i + 1; j < end; j++) {             if (arr[i] == arr[j]) {                                   int shiftLeft = j;                 for (int k = j+1; k < end; k++, shiftLeft++) {                     arr[shiftLeft] = arr[k];                 }                 end--;                 j--;             }         }     }     int[] whitelist = new int[end];     for(int i = 0; i < end; i++){         whitelist[i] = arr[i];     }     return whitelist;}

Answer 1

你可以求助于集收藏

int end = arr.length;Set<Integer> set = new HashSet<Integer>();for(int i = 0; i < end; i++){
  set.add(arr[i]);}

现在，如果您要迭代这个集，它将只包含唯一的值。迭代代码如下所示：

Iterator it = set.iterator();while(it.hasNext()) {
  System.out.println(it.next());}

Answer 2

注意：我假设数组是排序的。

代码：

int[] input = new int[]{1, 1, 3, 7, 7, 8, 9, 9, 9, 10};int current = input[0];boolean found = false;for (int i = 0; i < input.length; i++) {
    if (current == input[i] && !found) {
        found = true;
    } else if (current != input[i]) {
        System.out.print(" " + current);
        current = input[i];
        found = false;
    }}System.out.print(" " + current);

产出：

  1 3 7 8 9 10