Was ist der schnellste Algorithmus ein Element mit der höchsten Frequenz in einem Array

Question

Ich habe zwei Eingangs Arrays X und Y. ich das Element der Array X zurückkehren wollen zu finden, die in Array Y.

Die mit der höchsten Frequenz auftritt Eine naive Art, dies zu tun, erfordert, dass für jedes Element x von Array X linear das Array Y nach seiner Anzahl von Vorkommen durchsucht wird und dann das Element x, das die höchste Frequenz hat, zurückgegeben wird. Hier ist der Pseudo-Algorithmus:

max_frequency = 0 
max_x = -1    // -1 indicates no element found 
For each x in X 
    frequency = 0 
    For each y in Y 
     if y == x 
      frequency++ 
    End For 
    If frequency > max_frequency 
     max_frequency = frequency 
     max_x = x 
    End If 
End For 
return max_x 

Da es zwei verschachtelte Schleifen, Zeitkomplexität für diesen Algorithmus wäre O (n^2). Kann ich das in O (nlogn) oder schneller machen?

Answer 1

verwenden, um eine Hash-Tabelle, die Schlüssel zu zählt. Für jedes Element im Array, wie counts[element] = counts[element] + 1 oder das Äquivalent Ihrer Sprache.

Am Ende, durchlaufen Sie die Zuordnungen in der Hash-Tabelle und finden Sie die max.

Answer 2

Könnte einen Quicksort machen und dann mit einer Variablen durchqueren, die zählt, wie viele Zahlen in einer Reihe sind + was diese Zahl ist. Das sollte Sie geben nlogn

Answer 3

Merge Gestützte Sortierung auf Divide and Conquer Konzept gibt Ihnen O (n log n) Komplexität

Answer 4

Alternativ können Sie, wenn Sie weitere Datenstrukturen haben können, das Array Y durchlaufen, wobei jede Nummer ihre Häufigkeit in einer Hash-Tabelle aktualisiert. Dies dauert O(N(Y) Zeit. Gehe dann X und finde heraus, welches Element in X die höchste Frequenz hat. Dies dauert O(N(X)) Zeit. Gesamt: lineare Zeit, und da Sie jedes Element von sowohl X und Y in jeder Implementierung mindestens einmal betrachten müssen (EDIT: Dies ist streng genommen nicht in allen Fällen/alle Implementierungen zutreffend, wie jwpat7 weist darauf hin, obwohl es im schlimmsten Fall wahr ist), kannst du es nicht schneller machen.

Answer 5

Die Zeitkomplexität von gemeinsamen Algorithmen sind unten aufgeführt:

Algorithm  | Best | Worst | Average 
--------------+-----------+-----------+---------- 
MergeSort  | O(n lg n) | O(n lg n) | O(n lg n) 
InsertionSort | O(n) | O(n^2) | O(n^2) 
QuickSort  | O(n lg n) | O(n^2) | O(n lg n) 
HeapSort  | O(n lg n) | O(n lg n) | O(n lg n) 
BinarySearch | O(1) | O(lg n) | O(lg n) 

Im Allgemeinen, wenn durch eine Liste durchläuft ein bestimmten Kriterien zu erfüllen, kann man wirklich nicht besser als die lineare Zeit tun. Wenn Sie das Array sortieren müssen, würde ich sagen, bleiben Sie mit Mergesort (sehr zuverlässig), um das Element mit der höchsten Frequenz in einem Array zu finden.

Hinweis: Dies ist unter der Annahme, dass Sie einen Sortieralgorithmus verwenden möchten. Andernfalls, wenn Sie eine beliebige Datenstruktur verwenden dürfen, würde ich eine Hashmap/Hashtable-Struktur mit konstanter Nachschlagezeit verwenden. Auf diese Weise passen Sie nur die Schlüssel an und aktualisieren das Schlüssel-Wert-Paar der Häufigkeit. Hoffe das hilft.

Answer 6

Ihr vorgeschlagener Ansatz ist O (n^2), wenn beide Listen die Länge n haben. Wahrscheinlicher ist, dass die Listen unterschiedliche Längen haben können, so dass die Zeitkomplexität als O (mn) ausgedrückt werden könnte. 1.Order der einzigartigen Elemente von Y durch ihre Frequenz 2. Suchen Sie das erste Element aus dieser Liste, die

Wie das klingt wie eine Hausaufgabe Frage in X vorhanden ist:

Sie können Ihr Problem in zwei Phasen trennen Ich lasse dich darüber nachdenken, wie schnell du diese einzelnen Schritte machen kannst. Die Summe dieser Kosten ergibt die Gesamtkosten des Algorithmus. Es gibt viele Ansätze, die billiger als das Produkt der zwei Listenlängen sind, die Sie derzeit haben.

Answer 7

1. Schritt: Sortieren Sie beide X und Y. Unter der Annahme, dass ihre entsprechenden Längen m und n sind, wird die Komplexität dieses Schritts O(n log n) + O(m log m) sein.

2. Schritt: Zählen jedes X _i in Y und maximalen Zähler nachverfolgen bisher. Suche nach X _i in sortiert Y ist O(log n). Insgesamt 2. Schritt Komplexität ist:

Gesamtkomplexität: O(n log n) + O(m log m) + O(m log n) oder Simpified: O(max(n,m) log n)

Answer 8

sortieren X und Y. Dann sortieren Sie verschmelzen. Zählen Sie die Frequenzen von Y jedes Mal, wenn es auf dasselbe Element in X trifft.

Also Komplexität, O (nlogn) + O (mlogm) + O (m + n) = O (klogk) wo n, m = Länge von X, Y; k = max (m, n)