Solution Python au problème du nombre K maximum

Problème TopK, c'est-à-dire trouver le plus grand nombre K. Ce problème est très courant, comme trouver les 10 mots-clés les plus populaires parmi 10 millions d'enregistrements de recherche.

Méthode 1 :
Triez d'abord, puis interceptez les k premiers nombres
Complexité temporelle : O(n*logn) O(k)=O(n*logn).
Cette méthode est relativement simple et grossière, il suffit de la mentionner.

Méthode 2 : Max Heap

Nous pouvons créer un conteneur de données de taille K pour stocker les plus petits nombres K, puis parcourir l'ensemble du tableau et ajouter chaque nombre Comparez-le avec le nombre maximum dans le conteneur. Si ce nombre est supérieur à la valeur maximale dans le conteneur, continuez le parcours, sinon remplacez la valeur maximale dans le conteneur par ce nombre. La compréhension de cette méthode est également très simple. Quant au choix du conteneur, la première réaction de beaucoup de gens est le tas maximum. Mais comment implémenter le tas maximum en Python ? Nous pouvons utiliser la bibliothèque heapq qui implémente le tas minimum, car dans un tableau, si chaque nombre est inversé, le nombre maximum devient le nombre minimum et l'ordre du nombre entier change, donc chaque nombre du tableau peut être inversé. , puis utilisez le tas minimum pour annuler le résultat lors du retour final. Le code est le suivant :

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)

Méthode. 3 ：sélection rapide

algorithme de sélection rapide. En fait, il est similaire à la sélection rapide. La différence est que la sélection rapide ne doit aller que dans une seule direction pour chaque voyage.
Complexité temporelle : 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)

Pour plus d'articles liés à la version Python du problème du nombre K maximum, veuillez faire attention au site Web PHP chinois !