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



## H2SO4 (30. Sep 2009)

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 (30. Sep 2009)

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 (30. Sep 2009)

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 (1. Okt 2009)

Ganz spontan, ungetestet und inperformant:

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


----------



## 0x7F800000 (1. Okt 2009)

Landei hat gesagt.:


> 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 (1. Okt 2009)

Landei hat gesagt.:


> Ganz spontan, ungetestet und inperformant:
> 
> ```
> boolean hasDuplicates = new Set(Arrays.asList(array)).size() != array.length;
> ```



nice! gefällt mir!


----------



## Landei (1. Okt 2009)

0x7F800000 hat gesagt.:


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


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


----------



## Marco13 (1. Okt 2009)

@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 (1. Okt 2009)

Marco13 hat gesagt.:


> 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 (1. Okt 2009)

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 (1. Okt 2009)

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


----------



## 0x7F800000 (1. Okt 2009)

eRaaaa hat gesagt.:


> 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 (1. Okt 2009)

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 (1. Okt 2009)

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


----------



## SlaterB (1. Okt 2009)

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 (1. Okt 2009)

Und noch als Nachschl..trag:


0x7F800000 hat gesagt.:


> 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 (1. Okt 2009)

SlaterB hat gesagt.:


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


Marco13 hat gesagt.:


> 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


----------

