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

arrays optimization java

2022-08-31 15:48:29

我被要求编写自己的实现来删除数组中的重复值。这是我创造的。但是在对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;
}

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

答案 2

如果您被允许使用 Java 8 流：

Arrays.stream(arr).distinct().toArray();