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

Question

我被要求编写自己的实现来删除数组中的重复值。这是我创建的内容。但是在测试了100万个元素后，它需要很长时间才能完成。是否有什么方法可以改进我的算法或者消除任何错误？

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

---

你面临哪些限制？你能进行“排序”吗？你肯定可以改进这个O(n^3)的实现。这个算法在最优情况下应该是O(nln(n))。 - Boris the Spider

好的，你有一个O(n^3)的算法......这对我来说听起来不是一个好主意。 - Jon Skeet

你可以使用 Set<Integer> 吗？ - sanbhat

您在Codereview上也提出了这个问题。那里也有一个答案。 - user1907906

好的，您已经在code review forum中得到了两个答案。 - morgano

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

- Android Killer

---

我应该自己完成这个练习的实现。但还是谢谢你。 - ashur

OP明确表示他想要在不使用Set的情况下解决问题。请在回答之前仔细阅读问题。 - old_soul_on_the_run

我来这里寻找一种易于理解的方法，对我来说，它是设置或其他什么都无所谓。非常感谢您的帮助。 - Harshit Saxena

@goyalshub1509，在我回答时并没有写明他想要没有设置，所以我就那样回答了。 - Android Killer

但是问题本身说不要使用SET集合，那么为什么这个答案在这里？ - Angad Bansode

@AngadBansode，请在您的评论之前阅读我的回答。 - Android Killer

Answer 2

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

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

- Tomin

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

- Kick Buttowski

---

你假设这个数组已经排好序了，所以如果这个数组在随机位置有重复项或者是未排序的话程序就会出错。 - Say No To Censorship

如果数组已排序，可以通过异或运算更简单地完成。请查看我的答案。 - M Sach

假设数组已排序 - K.K

优秀的算法可以用于删除已排序数组中的重复元素。 - prajun7

Answer 4

通过删除最内层的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;
}

- Pavan Kumar

Answer 5

由于您可以假设范围在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)。需要注意的是，返回的数组是已排序的，如果这是不合法的，则此答案无效。

- Esailija

---

您的实现类似于桶排序算法。 - Say No To Censorship

“== false”和“== true”？听说过“！”吗？ - Clashsoft

为什么 == true？（摊手） - Ankur Verma

为什么我们要使用totalItems创建新数组，我们可以使用同一个数组来节省内存。以下是代码： int c = 0; for (int i = 0; i < arr.length; i++) { if (set[arr[i]]) { arr[c++] = arr[i]; System.out.println(arr[i]); set[arr[i]] = false; } } - Arnav Joshi

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

- user3752541

---

如果您解释一下您所做的事情，这样的答案对社区会更有帮助。 - Bmo

高效地去除重复项，但不是高效的排序 :-) - Anatolii Stepaniuk

Answer 7

这个问题有很多解决方案。

1. 排序方法

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

2. 集合方法

   • 声明一个 HashSet，将所有项目放入其中，然后只剩下唯一的项。

3. 创建一个布尔数组，表示已经返回的项（这取决于数组中的数据）。

如果你处理大量数据，我会选择第一种解决方案。因为你不需要分配额外的内存，而且排序速度相当快。对于小数据集，复杂度将是n^2，但对于大数据集，它将是n log n。

- Damian Leszczyński - Vash

Answer 8

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

您正在遵循与冒泡排序相同的哲学，这是非常非常慢的。您尝试过这个吗？：

• 使用快速排序对未排序的数组进行排序。快速排序比冒泡排序快得多（我知道，您没有进行排序，但是您遵循的算法几乎与冒泡排序遍历数组相同）。

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

- ashur

---

你能提供一些例子吗？ - Lion789

@Lion，请在此处检查代码 - https://gist.github.com/anil477/c2349420b7ebca121ef82ca30b771bcd - user3107673

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**

- Abhishek Anand

Answer 10

package com.pari.practice;

import java.util.HashSet;
import java.util.Iterator;

import com.pari.sort.Sort;

public class RemoveDuplicates {

 /**
 * brute force- o(N square)
 * 
 * @param input
 * @return
 */
public static int[] removeDups(int[] input){
    boolean[] isSame = new boolean[input.length];
    int sameNums = 0;

    for( int i = 0; i < input.length; i++ ){
        for( int j = i+1; j < input.length; j++){
            if( input[j] == input[i] ){ //compare same
                isSame[j] = true;
                sameNums++;
            }
        }
    }

    //compact the array into the result.
    int[] result = new int[input.length-sameNums];
    int count = 0;
    for( int i = 0; i < input.length; i++ ){
        if( isSame[i] == true) {
            continue;
        }
        else{
            result[count] = input[i];
            count++;
        }
    }

    return result;
}

/**
 * set - o(N)
 * does not guarantee order of elements returned - set property
 * 
 * @param input
 * @return
 */
public static int[] removeDups1(int[] input){
    HashSet myset = new HashSet();

    for( int i = 0; i < input.length; i++ ){
        myset.add(input[i]);
    }

    //compact the array into the result.
    int[] result = new int[myset.size()];
    Iterator setitr = myset.iterator();
    int count = 0;
    while( setitr.hasNext() ){
        result[count] = (int) setitr.next();
        count++;
    }

return result;
}

/**
 * quicksort - o(Nlogn)
 * 
 * @param input
 * @return
 */
public static int[] removeDups2(int[] input){
    Sort st = new Sort();
    st.quickSort(input, 0, input.length-1); //input is sorted

    //compact the array into the result.
    int[] intermediateResult = new int[input.length];
    int count = 0;
    int prev = Integer.MIN_VALUE;
    for( int i = 0; i < input.length; i++ ){
        if( input[i] != prev ){
            intermediateResult[count] = input[i];
            count++;
        }
        prev = input[i];
    }

    int[] result = new int[count];
    System.arraycopy(intermediateResult, 0, result, 0, count);

    return result;
}


public static void printArray(int[] input){
    for( int i = 0; i < input.length; i++ ){
        System.out.print(input[i] + " ");
    }
}

public static void main(String[] args){
    int[] input = {5,6,8,0,1,2,5,9,11,0};
    RemoveDuplicates.printArray(RemoveDuplicates.removeDups(input));
    System.out.println();
    RemoveDuplicates.printArray(RemoveDuplicates.removeDups1(input));
    System.out.println();
    RemoveDuplicates.printArray(RemoveDuplicates.removeDups2(input));
}
}

输出结果：5 6 8 0 1 2 9 11

0 1 2 5 6 8 9 11

0 1 2 5 6 8 9 11

我刚刚编写了上面的代码进行尝试。谢谢。

- user3222017