Prüfen, ob doppete Werte in int-Array vorhanden sind

[H2SO4]

Meine Frage steht ja eigentlich schon im Titel:

Gibt es eine elegante Möglichkeit zu überprüfen, ob sich in einem Array mit Zahlen (int), doppelte Werte befinden?

 

[hdi]

Mir fällt dazu nur ein, eine Liste mit der Wrapper-Klasse Integer zu nehmen und per .contains() zu prüfen. Listen sind zwar nicht so schnell wie Arrays, aber um herauszufinden ob eine Zahl in einem Array schon "gesichtet" wurde benötigt man ja sowieso irgendeine Art Liste, um solche Zahlen abzuspeichern...

Falls du unbedingt Listen vermeiden willst, musst du wohl warten bis jmd antwortet, der sich mit Algorithmen und Mathe gut auskennt, ich stell mich da immer etwas doof an

 

[eRaaaa]

hm, keine ahnung?! würde jetzt spontan das array sortieren, und die nachbarn prüfen?!

Arrays.sort(array);
		boolean hasDuplicates = false;
		for (int i = 0; i < array.length-1; i++) {
			if (array[i] == array[i + 1]) {
				hasDuplicates = true;
				break;
			}
		}
		System.out.println(hasDuplicates);

 

[Landei]

Ganz spontan, ungetestet und inperformant:

boolean hasDuplicates = new Set(Arrays.asList(array)).size() != array.length;

 

[0x7F800000]

Ganz spontan, ungetestet und inperformant

inperformant? Höchstens um einen konstanten Faktor


asList kostet O(n)
Set() kostet durchschnittlich O(n) wenn HashSet gemeint ist
längenvergleich kostet O(1)

insgesamt O(n)

Bei eRaaaa braucht man O(n*log(n)) zum sortieren.
Was hdi wollte weiß ich nicht so genau, schätzen wir das mal default-mäßig auf O(n^2)

Also von wegen "inperformant"

 

[ARadauer]

Ganz spontan, ungetestet und inperformant:

boolean hasDuplicates = new Set(Arrays.asList(array)).size() != array.length;

nice! gefällt mir!

 

[Landei]

Set() kostet durchschnittlich O(n) wenn HashSet gemeint ist

Ups, das kommt vom vielen Scala
Ja, ich hatte eigentlich an HashSet gedacht.

 

[Marco13]

@Landei: So eine Lösung hatte ich auch in Erwägung gezogen - die wäre natürlich elegant, in bezug auf die Laufzeit auch effizient, aber in bezug auf den Platz eben nicht - hier ist der Tradeoff zwischen
O(n) Zeit + O(n) Platz vs
O(n^2) Zeit + O(1) Platz
besonders offensichtlich.

Das viel größere Problem ist: Es funktioniert nicht Arrays.asList(array) liefert eine Liste, die einen int-array enthält. Einen int-arrays auf diese Weise zu einer Integer-List zu autoboxen funktioniert leider nicht.

 

[0x7F800000]

Das viel größere Problem ist: Es funktioniert nicht Arrays.asList(array) liefert eine Liste, die einen int-array enthält. Einen int-arrays auf diese Weise zu einer Integer-List zu autoboxen funktioniert leider nicht.

Es funktioniert doch: Arrays erben zwar von Object, bei varargs werden die aber wieder anders behandelt

import static java.util.Arrays.*;
import static java.lang.System.*;
import java.util.*;

public class _ {

	public static void main(String[] args) {
		String[] words={"xfchgvjb","cfhgv","cfhgvjb"};
		List<String> stringList=asList(words); 
		out.println(stringList+"\t"+stringList.size());
		List<?> arrayList = asList(((Object)words));
		out.println(arrayList+"\t"+arrayList.size());
	}

}

liefert

[xfchgvjb, cfhgv, cfhgvjb]	3
[[Ljava.lang.String;@1a46e30]	1

Tja, da sieht man wieder mal wunderbar, dass nicht mal Leute die seit kA... 10 Jahren ununterbrochen Java programmieren immer noch keine Ahnung haben, wie sich diese völlig bescheuerten Array benehmen :lol:

 

[eRaaaa]

was marco wohl sagen wollte ist, dass das ganze nicht mit einem int[] klappt, sondern nur mit Integer[] ! ?! oder hab ich was falsch verstanden? (denn asList macht bei übergabe von einem int[] eine liste mit einem int[] element, demzufolge ist dann die größe auch immer 1)

 

[Landei]

Hmmm, da sollte Sun nachbessern mit ein paar überladenen asList-Varianten...

 

[0x7F800000]

was marco wohl sagen wollte ist, dass das ganze nicht mit einem int[] klappt, sondern nur mit Integer[] ! ?! oder hab ich was falsch verstanden? (denn asList macht bei übergabe von einem int[] eine liste mit einem int[] element, demzufolge ist dann die größe auch immer 1)

Aaach scheiße! ;( Dieses Detail hab ich glatt übersehen^^ Egal, dann muss man einfach Marco13 durch mich, und ~10 Jahre durch ~4 Jahre ersetzen, dann gilt mein gemeiner Spruch bezüglich der bescheuerten Arrays immer noch :bae:

(shit, ich hab mir doch schon mal vorgenommen, Aussagen von Marco13 ohne eine richtig gründliche Untersuchung nicht anzuzweifeln, und dann sowas^^ )

Genau daher versuche ich nach möglichkeit keine int's statt Integer und keine Arrays statt ArrayLists zu benutzen, wenn's nicht unbedingt sein muss :autsch:

 

[H2SO4]

Find ich super, dass so eine Diskussion durch eine relativ "banale" Frage entstanden ist. Mir hat die Antwort von Landei sehr geholfen, danke. War genau das, was ich gesucht habe

 

[Marco13]

Obwohl sie nicht funktioniert?! ??? :L :bahnhof:

 

[SlaterB]

selbst mit etwas Arbeit ist

new Set()
for (int ..
set.add(Integer.valueof())
}

in der Situation noch das beste,
bei der Schleife kann man gar evtl. vorher abbrechen, wenn bereits ein Paar gefunden

 

[Marco13]

Und noch als Nachschl..trag:

Tja, da sieht man wieder mal wunderbar, dass nicht mal Leute die seit kA... 10 Jahren ununterbrochen Java programmieren immer noch keine Ahnung haben, wie sich diese völlig bescheuerten Array benehmen :lol:

Die varargs sind ja auch erst sehr spät dazugekommen (und manchmal ein bißchen hakelig speziell bei 'null' oder eben bei Arrays...)

 

[0x7F800000]

bei der Schleife kann man gar evtl. vorher abbrechen, wenn bereits ein Paar gefunden

speziell für SlaterB, der die vollständige Klammerung so sehr mag:

	public static boolean containsDuplicates(int[] arr){
		HashSet<Integer> set=new HashSet<Integer>();
		for(Integer i:arr) if(!set.add(i)) return true;
		return false;
	}

sowas ungefähr?
Dürfte im Schnitt um faktor 4 schneller laufen...

Die varargs sind ja auch erst sehr spät dazugekommen (und manchmal ein bißchen hakelig speziell bei 'null' oder eben bei Arrays...)

Jaajaja, und trotzdem: Landei hat was seltsames geschrieben, ich hab's geschluckt, ARadauer fand's sogar ganz toll^^ Und es ist ja auch nicht grad so, als ob alle drei 0 Plan von der Javasyntax hätten Das ist ein Indiz dafür, dass es eher an der Sprache liegt, als an den Menschen