java - 有一个算法问题想请教，给定一亿个数，如何用最快的方法取出其中最大的三个数。

Question

最近有一个java大神，是蚂蚁支付宝的哦，问了我这么一个问题。我的回答是先将数组分解成两百个小数组或者更多，在开两百个thread进行排序，取最大，然后对这两百个数进行排序，取前三。其实我的思路根本就没有涉及到算法层面，也只是暴力破解。其实这不是最好的做法，因为这样会严重的浪费资源，然后他的回答是堆排序。我的问题是堆排序是怎样实现的，最好用代码体现出来。

Answer 1

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.

Answer 2

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).

Answer 3

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...

Answer 4

N'est-ce pas une question typique de Top K ? Vous pouvez rechercher Top K sur Baidu

Answer 5

La réponse de topn est correcte si elle est empilée. La question est tirée de ce 3. . . Un si petit nombre

Answer 6

C'est une sorte de tas

Answer 7

solution top

Answer 8

Si vous voulez être le plus rapide, je pense que le tri bitmap est le plus rapide que j'ai jamais vu.