如何在不使用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&nbsp;end&nbsp;=&nbsp;arr.length;Set<Integer>&nbsp;set&nbsp;=&nbsp;new&nbsp;HashSet<Integer>();for(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;end;&nbsp;i++){ &nbsp;&nbsp;set.add(arr[i]);}现在，如果您要迭代这个集，它将只包含唯一的值。迭代代码如下所示：Iterator&nbsp;it&nbsp;=&nbsp;set.iterator();while(it.hasNext())&nbsp;{ &nbsp;&nbsp;System.out.println(it.next());}

Answer 2

注意：我假设数组是排序的。代码：int[]&nbsp;input&nbsp;=&nbsp;new&nbsp;int[]{1,&nbsp;1,&nbsp;3,&nbsp;7,&nbsp;7,&nbsp;8,&nbsp;9,&nbsp;9,&nbsp;9,&nbsp;10};int&nbsp;current&nbsp;=&nbsp;input[0];boolean&nbsp;found&nbsp;=&nbsp;false;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;input.length;&nbsp;i++)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(current&nbsp;==&nbsp;input[i]&nbsp;&&&nbsp;!found)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;found&nbsp;=&nbsp;true; &nbsp;&nbsp;&nbsp;&nbsp;}&nbsp;else&nbsp;if&nbsp;(current&nbsp;!=&nbsp;input[i])&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;System.out.print("&nbsp;"&nbsp;+&nbsp;current); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;current&nbsp;=&nbsp;input[i]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;found&nbsp;=&nbsp;false; &nbsp;&nbsp;&nbsp;&nbsp;}}System.out.print("&nbsp;"&nbsp;+&nbsp;current);产出：&nbsp;&nbsp;1&nbsp;3&nbsp;7&nbsp;8&nbsp;9&nbsp;10