Doppelte Werte aus einem Array entfernen

101836
ashur

Hier ist mein Code zum Entfernen doppelter Werte aus einem Array. Ich glaube, ich habe es mit den meisten möglichen Fällen getestet. Irgendwelche Vorschläge oder Fehler?

class duplicate {

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

Nach einigen Tests erscheint es wirklich ineffizient, da ein Array mit 1.000.000 Elementen sehr lange dauert. Gibt es eine bessere Möglichkeit, dies auf Arrays zu implementieren?

Antworten
11
Set verwenden (zB HashSet). Doppelte Werte sind nicht zulässig. Iterieren Sie einfach über das Array und fügen Sie es dem Set hinzu. Wenn Sie möchten, dass ein Array das Set zum Zielarray kopiert. Aniket Thakur vor 6 Jahren 2

3 Antworten auf die Frage

12
András Hummer

Suggestion:

public static Integer[] removeDuplicates(Integer[] arr) {
  return new HashSet<Integer>(Arrays.asList(arr)).toArray(new Integer[0]);
}

Another solution might be:

public static int[] removeDuplicates(int[] arr) {
  Set<Integer> alreadyPresent = new HashSet<Integer>();
  int[] whitelist = new int[0];

  for (int nextElem : arr) {
    if (!alreadyPresent.contains(nextElem)) {
      whitelist = Arrays.copyOf(whitelist, whitelist.length + 1);
      whitelist[whitelist.length - 1] = nextElem;
      alreadyPresent.add(nextElem);
    }
  }

  return whitelist;
}

Here you only iterate once via arr.

Sie können es vermeiden, die Whitelist für jedes eindeutige Element zu kopieren. Beginnen Sie damit, dass Sie dieselbe Größe wie das Original haben. Kopieren Sie dann das Unterfeld nur mit eindeutigen Elementen, bevor Sie zurückkehren. bowmore vor 6 Jahren 1
Die schrittweise Erhöhung der "Whitelist" um 1 führt zu einer zeitlichen Komplexität von ** `O (N ^ 2)` **. Erwägen Sie die Verwendung von ArrayList, die dynamisch erweitert wird, und geben Sie arraylist.toArray () zurück. `Das würde in **` O (N) `** laufen. recursion.ninja vor 6 Jahren 1
@awashburn Wenn Targeting> = .NET 2.0, sollte man `List verwenden`statt` ArrayList`. Mathieu Guindon vor 6 Jahren 0
11
bowmore

Eine leichte Verbesserung gegenüber Dr. H.

public static int[] removeDuplicates(int[] arr) {
    Set<Integer> alreadyPresent = new HashSet<>();
    int[] whitelist = new int[arr.length];
    int i = 0;

    for (int element : arr) {
        if (alreadyPresent.add(element)) {
            whitelist[i++] = element;
        }
    }

    return Arrays.copyOf(whitelist, i);
}

Dadurch wird am Ende nur eine Array-Kopie erstellt. Es nutzt auch die Tatsache, dass Set.add()ein boolescher Wert zurückgegeben wird, der angibt, ob sich das Set geändert hat, und eine explizite contains()Überprüfung vermieden wird .

Java 8-Update

In Java 8 ist der Code viel einfacher:

public static int[] removeDuplicates(int[] arr) {
    return Arrays.stream(arr)
            .distinct()
            .toArray();
}
Warum kopierst du die Whitelist? Können wir nicht einfach die Whitelist zurückgeben? Prabhat Subedi vor 4 Jahren 0
@PrabhatSubedi-Kopie, da die Größe (höchstwahrscheinlich) kleiner als das Original ist. Und die Whitelist hat die Originalgröße. bowmore vor 4 Jahren 0
10
morgano

You're following the same philosophy as the bubble sort, which is very, very, very slow. Have you tried this?:

  • Sort your unordered array with quicksort. Quicksort is much faster than bubble sort (I know, you are not sorting, but the algorithm you follow is almost the same as bubble sort to traverse the array).
  • Then start removing duplicates (repeated values will be next to each other). In a for loop you could have two indices: source and destination. (On each loop you copy source to destination unless they are the same, and increment both by 1). Every time you find a duplicate you increment source (and don't perform the copy).