HashMap mit ganzen Zahlen lange Zeit

-2

Ich habe eine Reihe von Zahlen von 0 bis die Länge des Arrays, mit der Ausnahme, dass eine gewisse Anzahl fehlt, und ich habe es zu finden.HashMap mit ganzen Zahlen lange Zeit

public static Integer findNumber(Integer[] array){ 
    Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 
    for(Integer number : array){ 
     map.put(number, 1); 
    } 
    for(Integer i=0; i<array.length; i++){ 
     if(map.get(i)==null) 
      return i; 
    } 
    return -1; 
}

Ich dachte, dies würde eine gute Lösung sein, aber eine wirklich lange Zeit in Anspruch nimmt setzen, mit dem Zählen Duplikaten Sortier Lösung viel schneller ist, und ich habe keine Ahnung, warum. Hash für Integer ist, dass Integer selbst, so ist es nicht einmal Zeit zu zählen Hash verloren, und kein Iterieren mit equals (das hängt von Zahlen, nahm ich ein Beispiel mit nur einem einzigen Duplikat). Ich fühle mich, als würde ich hier etwas Offensichtliches vermissen. Ich habe versucht, Anfangskapazität und Ladefaktor anzugeben, aber es macht nur noch schlimmer. Kann ich das irgendwie optimieren?

Es setzen, dass viel Zeit in Anspruch nimmt, nicht Lösung zu finden iterieren, Putting ist wie 95% der Zeit der Ausführung.

Quelle

2016-07-11 Haratino

Könnte langsam sein wegen einer Menge Boxen/Unboxing passiert? – kaqqao

Ein Set wird etwas schneller als eine Karte sein. –

Ich dachte auch, ich begann mit primitiven Ints, änderte dann für Integer, änderte überhaupt nichts. Ich denke, selbst wenn es die Dinge langsamer macht, macht es sie nicht so viel langsamer. – Haratino

-1

Ich denke, es gibt eine einfachere Lösung. Versuchen Sie dies:

public static Integer findNumber(Integer[] array){ 

    for(Integer i=0; i<array.length; i++){ 
     if(i != array[i]) 
      return i; 
    } 
    return -1; 
}

Hoffnung, die Ihnen helfen wird.

Quelle

2016-07-11 09:20:25 mrk

ich glaube nicht, dass funktioniert, Beispiel: 'array = {2,1,3}' die fehlende Zahl 0 sein soll, aber wird Ihr Code 2 zurück – niceman

weder diesen Code behandelt doppelte Nummern oder unsortiert Arrays. – Tom

Richtig, Niceman, ich habe das Problem nicht sehr gut verstanden. Aber nach einigen Recherchen denke ich, was er sucht ist (mathematisch) beantwortet hier [http://stackoverflow.com/questions/2113795/quickest-way-to-find-missing-number-in-an-array-of-numbers ] (http://stackoverflow.com/questions/2113795/quickest-way-to-find-missing-number-in-a-array-of-numbers) – mrk

statt Karte, können Sie eine Reihe von (primitiv) boolean verwenden. in der ersten Schleife, anstatt 1 setzen Sie die Array-Zelle auf true Flip: boolArray[number] = true;

danach, Schleife auf dem Array und finden Sie die fehlende Zahl

Quelle

2016-07-11 09:21:37

Ja, das ist eigentlich die Idee, die ich mit einer Karte erreichen wollte und ich dachte Karte würde so schnell wie diese, vielleicht auch nur ein wenig langsamer sein, weil es fast die gleiche Sache unter der Haube hat, sagen sie, ich Nummer 20 in einer Karte setzen, es Hash zählt, die das gleiche ist und es dann ist internalArray [20] = 1, was wie boolArray [number] = true ist. – Haratino

der Unterschied ist, dass, nachdem Sie das Bool Array füllen Sie es statt der Anzahl Array iterieren, meine andere Antwort sehen - auf die Werte der Karte iterieren für die Null –

wenn Sie sich mit der Karte bestehen: die zweite Schleife sollte geht nicht über das Array, sondern über die Werte der Karte, die Suche nach dem null-one:

map.values().stream().filter(v -> v == null).findFirst();

Quelle

2016-07-11 09:30:57

Sie gehen können einfacher und schnelle Art und Weise: Summe ganzer Zahlen in der Matrix und dann subtrahieren von (es ist die Summe der Anzahl von 1 bis n). Restwert ist die Nummer, die es fehlt.

Quelle

2016-07-11 09:38:21 kkonrad

Wie viele dieser Rätsel zu suchen ist es ein mathematischer Trick sie sind auf der Suche nach, nicht eine Programmierung. +1 –

HashMap mit ganzen Zahlen lange Zeit

Antwort

Verwandte Themen