Pourquoi devons-nous trier les trois premiers ? Ouvrez simplement trois nouveaux espaces variables pour enregistrer les résultats intermédiaires.
La complexité de cette méthode est O(nk), n est la quantité totale de données et k est le nombre de données à obtenir. Le tri est O(nlogn) qu'il s'agisse d'un tri en tas ou d'un tri rapide. Il y a toujours un avantage lorsque k est plus petit que log(2, 10 ** 8) S'il est trop grand, il dégénérera en tri par insertion.
Il existe N (N>>10000) entiers, trouvez parmi eux les K plus grands nombres. (Appelé problème de l'algorithme Top k). En raison de (1) une grande quantité de données d'entrée ; (2) uniquement les premiers K, il n'est pas souhaitable de sauvegarder et de trier l'intégralité des données d'entrée. Ce problème peut être résolu en utilisant un minimum de structures de données.
Tas minimum, la valeur de chaque nœud non-feuille ne doit pas être supérieure à la valeur du nœud enfant. De cette façon, un tas minimum contenant K nœuds peut être utilisé pour enregistrer les K valeurs maximales actuelles (bien sûr, le nœud racine est la valeur minimale parmi elles). Chaque fois qu'il y a une entrée de données, elles peuvent d'abord être comparées au nœud racine. Si elle n'est pas supérieure au nœud racine, supprimez-la ; sinon, remplacez la valeur du nœud racine par la nouvelle valeur. Et ajustez le tas minimum.
Puisque seuls K éléments de données sont enregistrés, la complexité temporelle du tas minimum est ajustée à O(logK), donc la complexité temporelle de l'algorithme TOp K (problème) est O(nlogK).
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
Pourquoi devons-nous trier les trois premiers ? Ouvrez simplement trois nouveaux espaces variables pour enregistrer les résultats intermédiaires.
La complexité de cette méthode est
O(nk), n est la quantité totale de données et k est le nombre de données à obtenir. Le tri estO(nlogn)qu'il s'agisse d'un tri en tas ou d'un tri rapide. Il y a toujours un avantage lorsque k est plus petit quelog(2, 10 ** 8)S'il est trop grand, il dégénérera en tri par insertion.Il existe N (N>>10000) entiers, trouvez parmi eux les K plus grands nombres. (Appelé problème de l'algorithme Top k). En raison de (1) une grande quantité de données d'entrée ; (2) uniquement les premiers K, il n'est pas souhaitable de sauvegarder et de trier l'intégralité des données d'entrée. Ce problème peut être résolu en utilisant un minimum de structures de données.
Tas minimum, la valeur de chaque nœud non-feuille ne doit pas être supérieure à la valeur du nœud enfant. De cette façon, un tas minimum contenant K nœuds peut être utilisé pour enregistrer les K valeurs maximales actuelles (bien sûr, le nœud racine est la valeur minimale parmi elles). Chaque fois qu'il y a une entrée de données, elles peuvent d'abord être comparées au nœud racine. Si elle n'est pas supérieure au nœud racine, supprimez-la ; sinon, remplacez la valeur du nœud racine par la nouvelle valeur. Et ajustez le tas minimum.
Puisque seuls K éléments de données sont enregistrés, la complexité temporelle du tas minimum est ajustée à O(logK), donc la complexité temporelle de l'algorithme TOp K (problème) est O(nlogK).
Recherchez simplement
http://www.cnblogs.com/skywang12345/p/3610187.html
Pour la preuve et la dérivation, voir Introduction aux algorithmes
Mais vous n'avez pas besoin d'empiler, après tout, vous ne cherchez que 3 numéros...
N'est-ce pas une question typique de Top K ? Vous pouvez rechercher Top K sur Baidu
La réponse de topn est correcte si elle est empilée. La question est tirée de ce 3. . . Un si petit nombre
C'est une sorte de tas
solution top
Si vous voulez être le plus rapide, je pense que le tri bitmap est le plus rapide que j'ai jamais vu.