如何在不使用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;
}

Answer 1

你可以借助Set系列的帮助

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

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

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

Answer 3

注意:我假设数组已排序.

码:

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

Answer 4

由于您可以假设范围介于0-1000之间,因此可以使用非常简单有效的解决方案

//Throws an exception if values are not in the range of 0-1000
public static int[] removeDuplicates(int[] arr) {
    boolean[] set = new boolean[1001]; //values must default to false
    int totalItems = 0;

    for (int i = 0; i < arr.length; ++i) {
        if (!set[arr[i]]) {
            set[arr[i]] = true;
            totalItems++;
        }
    }

    int[] ret = new int[totalItems];
    int c = 0;
    for (int i = 0; i < set.length; ++i) {
        if (set[i]) {
            ret[c++] = i;
        }
    }
    return ret;
}

这以线性时间O(n)运行.警告:返回的数组已排序,如果这是非法的,则此答案无效.

Answer 5

通过删除最里面的for循环,对原始代码本身进行轻微修改.

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];
                }*/
                arr[j] = arr[end-1];
                end--;
                j--;
            }
        }
    }

    int[] whitelist = new int[end];
    /*for(int i = 0; i < end; i++){
        whitelist[i] = arr[i];
    }*/
    System.arraycopy(arr, 0, whitelist, 0, end);
    return whitelist;
}

Answer 6

class Demo 
{
    public static void main(String[] args) 
    {
        int a[]={3,2,1,4,2,1};
        System.out.print("Before Sorting:");
        for (int i=0;i<a.length; i++ )
        {
            System.out.print(a[i]+"\t");
        }
        System.out.print ("\nAfter Sorting:");
        //sorting the elements
        for(int i=0;i<a.length;i++)
        {
            for(int j=i;j<a.length;j++)
            {
                if(a[i]>a[j])
                {
                    int temp=a[i];
                    a[i]=a[j];
                    a[j]=temp;
                }

            }
        }

        //After sorting
        for(int i=0;i<a.length;i++)
        {
            System.out.print(a[i]+"\t");
        }
        System.out.print("\nAfter removing duplicates:");
        int b=0;
        a[b]=a[0];
        for(int i=0;i<a.length;i++)
        {
            if (a[b]!=a[i])
            {
                b++;
                a[b]=a[i];
            }
        }
        for (int i=0;i<=b;i++ )
        {
            System.out.print(a[i]+"\t");
        }
    }
}
  OUTPUT:Before Sortng:3 2 1 4 2 1 After Sorting:1 1 2 2 3 4 
                Removing Duplicates:1 2 3 4

Answer 7

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

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

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

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

Answer 8

这个问题存在很多解决方案.

1. 排序方法

   • 您对数组进行排序并仅解析唯一项

2. 设定的方法

   • 你声明一个HashSet,你放置所有项目,然后你只有唯一的项目.

3. 您创建一个布尔数组,表示所有准备好的项目(这取决于您在数组中的数据).

如果您处理大量数据,我会选择1.解决方案.由于您没有分配额外的内存,因此排序速度非常快.对于小的数据集,复杂度将是n ^ 2但是对于大的i将是n log n.

Answer 9

import java.util.Arrays;

public class Practice {

public static void main(String[] args) {
    int a[] = { 1, 3, 3, 4, 2, 1, 5, 6, 7, 7, 8, 10 };
    Arrays.sort(a);
    int j = 0;
    for (int i = 0; i < a.length - 1; i++) {
        if (a[i] != a[i + 1]) {
            a[j] = a[i];
            j++;
        }
    }
    a[j] = a[a.length - 1];
    for (int i = 0; i <= j; i++) {
        System.out.println(a[i]);
    }

}
}
**This is the most simplest way**