So entfernen Sie Duplikate effizient aus einem Array, ohne Set zu verwenden

Lesezeit: 4 Minuten

So entfernen Sie Duplikate effizient aus einem Array ohne Set
ashur

Ich wurde gebeten, meine eigene Implementierung zu schreiben, um doppelte Werte in einem Array zu entfernen. Hier ist, was ich erstellt habe. Aber nach Tests mit 1.000.000 Elementen hat es sehr lange gedauert, bis es fertig war. Kann ich etwas tun, um meinen Algorithmus zu verbessern oder irgendwelche Fehler zu entfernen?

Ich muss meine eigene Implementierung schreiben – nicht verwenden Set, HashSet usw. Oder andere Tools wie Iteratoren. Einfach ein Array, um Duplikate zu entfernen.

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

  • Welche Einschränkungen werden Ihnen auferlegt? Können Sie sort? Sie können diese O(n^3)-Implementierung sicherlich verbessern. Dieser Algorithmus sollte im optimalen Fall O(nln(n)) sein.

    – Boris die Spinne

    31. Juli 2013 um 9:52 Uhr


  • Nun ja, Sie haben einen O (n ^ 3) -Algorithmus … das klingt für mich nicht nach einer guten Idee.

    – Jon Skeet

    31. Juli 2013 um 9:52 Uhr


  • Sie können verwenden Set<Integer> ?

    – Sanbhat

    31. Juli 2013 um 9:52 Uhr

  • Du hast das hier reingefragt Code-Review, zu. Es gibt eine Antwortzu.

    Benutzer1907906

    31. Juli 2013 um 9:53 Uhr


  • Nun, Sie haben bereits zwei Antworten in der Code-Review-Forum

    – Morgano

    31. Juli 2013 um 10:02 Uhr

Wenn Sie Java 8-Streams verwenden dürfen:

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

  • Danke, das funktioniert einwandfrei

    – NASSIM ADRAO

    27. Februar um 15:37 Uhr

  • Sie gehen davon aus, dass das Array sortiert ist, sodass es fehlschlägt, wenn das Array an zufälligen Stellen Duplikate enthält oder unsortiert ist.

    – Sag Nein zur Zensur

    8. April 2015 um 22:42 Uhr


  • @kick Butowski Nun, wenn das Array sortiert ist, kann es mit der XOR-Operation viel einfacher gemacht werden. Siehe meine Antwort

    – M Sach

    24. August 2016 um 13:20 Uhr

  • geht davon aus, dass das Array sortiert ist

    – KK

    24. Mai 2017 um 22:26 Uhr

Leichte Modifikation des ursprünglichen Codes selbst, indem die innerste for-Schleife entfernt wird.

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

1646317030 640 So entfernen Sie Duplikate effizient aus einem Array ohne Set
Petrow Dmitrij

Da Sie davon ausgehen können, dass der Bereich zwischen 0-1000 liegt, gibt es eine sehr einfache und effiziente Lösung

//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;
}

Dies läuft in linearer Zeit O(n). Vorbehalt: Das zurückgegebene Array ist sortiert. Wenn dies also illegal ist, ist diese Antwort ungültig.

1646317030 767 So entfernen Sie Duplikate effizient aus einem Array ohne Set
Arsen Dawtyan

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

  • Antworten wie diese sind für die Community viel hilfreicher, wenn Sie ein wenig erklären, was Sie getan haben.

    – Bmo

    18. Juni 2014 um 13:05 Uhr

  • Effizientes Entfernen von Duplikaten, aber kein effizientes Sortieren 🙂

    – Anatolii Stepaniuk

    9. August 2017 um 6:53 Uhr

924230cookie-checkSo entfernen Sie Duplikate effizient aus einem Array, ohne Set zu verwenden

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy