Duplikate im Array finden?
Hab hier nen Java Code, der nicht das richtige Ergebnis ausgibt. Was stimmt hier nicht? Wieso wird hier nicht korrekt berechnet, wie viele Zahlen im Array doppelt vorkommen?
4 Antworten
Hey,
die Schleife geht zwar durch jedes Element, aber Du vergleichst einfach nur data an der Stelle i mit data an der Stelle i+1 (das macht i++)
Außerdem bringt doch i++ deine Schleife durcheinander, denn i++ ist kurz für
i=i+1 und damit wird deine Zählvariable i auch geändert
Im Grunde musst Du für jeden Array Wert prüfen, ob dieser überhaupt noch mal im Array vorkommt, also alles ansehen und vergleichen, bis auf den Wert an der Stelle des Index selbst.
Oder Du sortierst erst das Array. Oder Du packst alles in eine Map, das hat dann Laufzeit O(n) statt O(n^2) (im Falle einer geschachtelten Schleife von 0 bis n-1) oder O(n log(n)) (im Falle von Sortieren)
Gruß
Kann man ausprobieren.
Ich vermute mal bei 100k lohnt es schon. Oder was heißt schon lohnen, es wäre schneller. Ob die Zeitersparnis lohnt kommt auf den konkreten Fall an.
Gruß
Das array wird bereits sortiert. XD Erste zeile gleich am anfang des methodenblockes.
die Schleife geht zwar durch jedes Element, aber Du vergleichst einfach nur data an der Stelle i mit data an der Stelle i+1 (das macht i++)
Das ist kein Problem, denn das Array wird ja vorher sortiert.
Arrays.sort(data);
Das Problem liegt bei
data[i++]
denn dadurch wird i gleich zweimal pro Durchlauf hochgesetzt. Durch
data[i+1]
sollte sich das Problem erübrigen.
Ah guck an, das sort habe ich gar nicht gesehen.
Ich denke trotzdem nicht, dass der Algo funktioniert, wenn Werte 3-4 mal vorkommen.
Ist die Frage was "doppelt" genau heißt. Nur doppelt, oder auch mehrfach? Kommt vier mal die Zahl 2 vor, wird das dann als zwei mal doppelt gezählt?
Gruß
Darüber gibt seine Fragestellung keine Auskunft, daher setze ich voraus, dass sein Algo so gedacht ist, wie er dort steht und das Problem in der Syntax zu suchen ist.
Wenn z.B. 4x die 2 vorkommt, würde er sie 3x als doppelt ansehen. Wenn du also zum Beispiel das Array
{1,2,2,2,2,3,4,5,5,5,6,7,8,8,8,9}
hast, dann liefert die Funktion den Wert 7 zurück. Von 16 Werten insgesamt, waren 7 mehrfach vorhanden.
Wenn er lediglich nur den Wert 3 haben möchte für 2, 5 und 8 dann wäre der Algo so natürlich schlecht. :)
Ist garantiert das das Array auch der größe nach geordnet ist?
- wie ultrarunner schon gesagt hat. Du erhöhst i zweimal. mach aus data[i++] ein data[i+1] dann siehst besser aus.
- Wie in der frage schon angedeutet funktioniert deine methode nur bei der größe nach geordneten arrays.
Als bespiel:
liefere ich das array:
1 3 4 3 5 6 3
Liefert dir deine methode als ergeniss 0 zurück.
Ein weiteres problem ist. Deine methode liefert dir nicht unbedingt die anzahl der doppelten zurück.
Als beispiel:
1222345
Würdest du hier das ergebnis 1 oder 2 erwarten?
Deine methode liefert dir hier das ergebniss 2.
EDIT: hab das mit dem sortieren übersehen. Dann kannst du die kritik ignorieren die sich auf unsortierte arrays bezieht.
Dennoch liefert der dir bei einem array mit 1222345 als ergebbniss 2 zurück.
Weil du die Variable i in jedem Schleifendurchlauf zweimal erhöhst.
Du hast recht i++ ist i + 1 aber das inkrementieren ist eine Anweisung. Das heißt du musst i + 1 angeben, damit nur der Wert übergeben wird, aber dabei nicht i dauerhaft um 1 erhöht wird 😉
Nein
i++ ist das selbe wie i = i + 1
nicht das selbe wie i+1
Riesen Unterschied. Bei i++ wird i verändert.
ich dachte i++ ist gleich i+1
Vom Wert her ist das auch so. Der Unterschied ist, dass i++ nicht nur den Wert i+1 zurückliefert, sondern diesen erhöhten Wert auch wieder in die Variable i zurückspeichert. Das macht einen kleinen Unterschied …
Eigentlich ist ++i = i + 1 gleichzusetzen. Bei ++i wird nämlich erst die Inkrementierung durchgeführt und dann der Rest der Zeile interpretiert und bei i++ wird erst die Zeile interpretiert und erst zum Schluss inkrementiert.
Bei i + 1 wird ja auch direkt inkrementiert.
Außerdem suchst du nur danach, ob zwei Werte hintereinander doppelt auftreten (nur i und i++ also i + 1).
Das ist kein Problem, die Liste ist ja sortiert. Ein schlauer Trick eigentlich.
Du darfst nicht data.length -1 angeben.
Das könnte eine Ursache sein.
Nein. .length gibt die Länge an. [1,2,3,4,5] hat eine length von 5.
Da aber der Array-Index bei 0 los geht würde ein index von 5 schon außerhalb des Bereichs liegen
Ich denke extra eine Map zu erstellen ist bei kleinen Arrays (schätze mal so < 100.000 Einträge) aber viel ineffizienter, als der Algorithmus den er hier hat. Ich teste es mal.