Finden Sie die N-te häufigste Zahl im array

Find the nth most frequent number in array.
(There is no limit on the range of the numbers)

Ich denke, wir können

(i) speichern Sie das auftreten von jedem element über die maps in C++

(ii) erstellen eines Max-Heaps in linearer Zeit der Ereignisse(oder Frequenz) des Elementes und extrahieren Sie dann bis zu dem N-TEN element,
Jeder Extraktion log(n) Zeit zu heapify.

(iii) erhalten wir die Frequenz des N-TEN häufigste Anzahl

(iv), dann können wir lineare Suche durch den hash zu finden, das element mit dieser Frequenz.

Zeit O(NlogN)
Space - O(N)

Gibt es eine bessere Methode ?

  • Siehe "Auswahl" - Algorithmus, die es erlaubt, zu wählen Sie das N-te element aus und sortierten array in O(N).
  • Die Frage ist, wählen Sie n-TEN die meisten FREQUENZ-Zahl und nicht N-te element.
  • ja, Schritt ich immer noch erforderlich, aber dann die Schritte ii, iii und iv ersetzt werden kann durch die Auswahl-Algorithmus ist O(N), die sich in einer Lösung, die O(N) weltweit.
InformationsquelleAutor Luv | 2012-06-10
  1. 3

    Ihre Methode ist grundsätzlich richtig. Sie vermeiden wollen, dass die endgültige hash-Suche, wenn Sie daneben bei dem jeder Knoten der heap konstruiert mit der Zahl die es repräsentiert. Darüber hinaus ist es möglich, ständig beobachten das fünfte element des Heaps, als Sie bauen Sie, weil Sie an einem Punkt, den Sie bekommen können, um eine situation, wo der Ausgang sich nicht mehr ändern und der rest der Berechnung gezogen werden kann. Aber dies würde wahrscheinlich nicht, dass der Algorithmus schneller in den Allgemeinen Fall, und vielleicht nicht einmal in besonderen Fällen. Also Sie beantwortet Ihre eigene Frage richtig.

    InformationsquelleAutor Boris Stitnicky
  2. 8

    Es getan werden kann in der linearen Zeit und Raum. Sei T die Gesamtzahl der Elemente in der Eingabe-array, aus dem wir zu finden der N-TEN häufigste Zahl:

    1. Zählen und speichern die Häufigkeit jeder Zahl in T in einer Karte. Sei M die Gesamtzahl von Elementen in dem array. Also, die Größe der Karte ist M. -- O(T)
    2. Finden Nth größte Frequenz bei anzeigen mit Auswahl-Algorithmus. -- O(M)

    Gesamtzeit = O(T) + O(M) = O(T)

    InformationsquelleAutor Garima
  3. 1

    Es hängt davon ab, ob Sie möchten, effektivsten, oder die meisten einfach-zu-schreiben-Methode.

    1) wenn Sie wissen, dass alle zahlen von 0 bis 1000 sein, Sie nur ein array mit 1000 Nullen (Ereignisse), eine Schleife durch das array und erhöhe den rechten position auftreten. Dann Sortieren Sie diese Ereignisse, und wählen Sie das N-te Wert.

    2) haben Sie eine "Tasche", einzigartige Elemente, die Sie Durchlaufen Ihre zahlen prüfen, ob die Zahl wird in eine Tasche, wenn nicht, fügen Sie es, wenn es da ist, werden Sie nur erhöhen die Anzahl der vorkommen. Dann Holen Sie sich eine N-te kleinste Zahl aus.

    Tasche kann linear array, BST oder Wörterbuch (hash-Tabelle).

    Ist die Frage "N-th häufigsten", so dass ich denke, man kann nicht vermeiden, Sortieren (oder clever-Daten-Struktur), also am besten Komplexität kann nicht besser als O(n*log(n)).

    • Methode 1 ist nicht wirklich zutreffend, da sich das Spektrum der Zahl nicht eine Grenze haben. In Methode 2, Kommissionierung N-te kleinste kann getan werden, auf Durchschnittliche Zeit Komplexität O(K) (wobei K die Anzahl der eindeutigen Elemente) mit Auswahl-Algorithmus: STL algorithm's nth_element Funktion. Die "Tasche" kann map aus STL-wie der OP erwähnt hat (STL map ist besser als normal BST, da map umgesetzt wird, wie self-balanced tree).
    • nhahtdh: Kommissionierung N-te kleinste von K zahlen, kann nicht sein getan in O(K). Sie müssen mindestens Sortieren Sie diese oder eine Schleife mit N-item-Haufen ... was ist die "Tasche" war ich Rede.
    • Wenn Sie nur suchen für die "N-te element" oder "Auswahl Algorithmus", werden Sie sehen, was ich meine.
    InformationsquelleAutor Ivan Kuckir
  4. 1

    Gerade geschrieben eine Methode, die in Java8: Dies ist keine effiziente Lösung.

    • Erstellen einer Frequenz-Zuordnung für jedes element
    • Sortieren den Inhalt der Karte auf Grundlage der Werte in umgekehrter Reihenfolge.

    • Überspringen Sie die (N-1) - te element, dann finden Sie das erste element

      private static Integer findMostNthFrequentElement(int[] inputs, int frequency) {
    return Arrays.stream(inputs).boxed()
        .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
        .entrySet().stream().sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
        .skip(frequency - 1).findFirst().get().getKey();
}
    InformationsquelleAutor nayakam
Schreibe einen Kommentar