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

Question

我被要求编写自己的实现来删除数组中的重复值。这是我创建的。但是在对 1,000,000 个元素进行测试后，需要很长时间才能完成。我可以做些什么来改进我的算法或删除任何错误吗？

我需要编写自己的实现 - 不要 使用 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;
}

原文由 ashur 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

由于这个问题仍然受到很多关注，我决定通过 从 Code Review.SE 复制这个答案 来回答它：

您遵循与冒泡排序相同的理念，它非常、非常、非常慢。你试过这个吗？：

• 使用 quicksort 对无序数组进行排序。 Quicksort 比冒泡排序快很多（我知道，你不是在排序，但是你遵循的算法几乎和冒泡排序一样遍历数组）。

• 然后开始删除重复项（重复值将彼此相邻）。在 for 循环中，您可以有两个索引： source 和 destination 。 （在每个循环中，您将 source 复制到 destination 除非它们相同，并将两者递增 1）。每次找到重复项时，您都会增加源（并且不执行复制）。 @摩根诺

原文由 ashur 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

你可以借助 Set collection

 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());
}

原文由 Android Killer 发布，翻译遵循 CC BY-SA 3.0 许可协议