Python-Lösung für das Problem der maximalen K-Zahl

TopK-Problem, d. h. das Finden der größten K-Zahl. Dieses Problem kommt sehr häufig vor, z. B. das Finden der 10 beliebtesten Schlüsselwörter aus 10 Millionen Suchdatensätzen.

Methode 1:
Zuerst sortieren und dann die ersten k Zahlen abfangen.
Zeitkomplexität: O(n*logn)+O(k)=O(n*logn).
Diese Methode ist relativ einfach und grob, erwähnen Sie sie einfach.

Methode 2: Max Heap

Wir können einen Datencontainer der Größe K erstellen, um die kleinsten K-Zahlen zu speichern, und dann das gesamte Array durchlaufen und jede Zahl hinzufügen Vergleichen Sie es mit der maximalen Zahl im Container. Wenn diese Zahl größer als der maximale Wert im Container ist, fahren Sie mit dem Durchlaufen fort. Andernfalls ersetzen Sie den maximalen Wert im Container durch diese Zahl. Das Verständnis dieser Methode ist ebenfalls sehr einfach. Was die Wahl des Containers betrifft, ist die erste Reaktion vieler Menschen der maximale Heap. Aber wie implementiert man den maximalen Heap? Wir können die Heapq-Bibliothek verwenden, die den minimalen Heap implementiert, denn wenn in einem Array jede Zahl invertiert wird, wird die maximale Zahl zur minimalen Zahl und die Reihenfolge der gesamten Zahl ändert sich, sodass jede Zahl im Array invertiert werden kann. , und verwenden Sie dann den minimalen Heap, um das Ergebnis zu negieren, wenn Sie es schließlich zurückgeben. Der Code lautet wie folgt:

import heapq
def get_least_numbers_big_data(self, alist, k):
  max_heap = []
  length = len(alist)
  if not alist or k <= 0 or k > length:
    return
  k = k - 1
  for ele in alist:
    ele = -ele
    if len(max_heap) <= k:
      heapq.heappush(max_heap, ele)
    else:
      heapq.heappushpop(max_heap, ele)

  return map(lambda x:-x, max_heap)


if __name__ == "__main__":
  l = [1, 9, 2, 4, 7, 6, 3]
  min_k = get_least_numbers_big_data(l, 3)

Methode 3:Schnellauswahl

Schnellauswahlalgorithmus In der Tat ähnelt es der Schnellauswahl. Der Unterschied besteht darin, dass die Schnellauswahl für jede Fahrt nur in eine Richtung gehen muss.
Zeitkomplexität: O(n).

def qselect(A,k): 
  if len(A)<k:return A 
  pivot = A[-1] 
  right = [pivot] + [x for x in A[:-1] if x>=pivot] 
  rlen = len(right) 
  if rlen==k: 
    return right 
  if rlen>k: 
    return qselect(right, k) 
  else: 
    left = [x for x in A[:-1] if x<pivot] 
    return qselect(left, k-rlen) + right 
 
for i in range(1, 10): 
  print qselect([11,8,4,1,5,2,7,9], i)

Weitere Artikel zur Python-Version des Problems mit der maximalen K-Zahl finden Sie hier zur chinesischen PHP-Website!