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

Question

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

Answer 1

Mengapa kita perlu mengisih tiga teratas? Hanya buka tiga ruang pembolehubah baharu untuk menyimpan hasil perantaraan.

Kerumitan kaedah ini ialah O(nk), n ialah jumlah data, dan k ialah bilangan data yang akan diperolehi. Pengisihan ialah O(nlogn) sama ada pengisihan timbunan atau pengisihan pantas. Masih ada kelebihan apabila k lebih kecil daripada log(2, 10 ** 8) Jika terlalu besar, ia akan merosot kepada jenis sisipan.

Answer 2

Terdapat N (N>>10000) integer, cari nombor K teratas terbesar di antaranya. (Dipanggil masalah algoritma Top k). Disebabkan oleh (1) sejumlah besar data input; (2) hanya K pertama, adalah agak tidak diingini untuk menyimpan dan mengisih keseluruhan data input. Masalah ini boleh dikendalikan menggunakan timbunan min struktur data.

Timbunan minimum, nilai setiap nod bukan daun mestilah tidak lebih besar daripada nilai nod anak. Dengan cara ini, timbunan minimum yang mengandungi nod K boleh digunakan untuk menyimpan nilai maksimum semasa K (sudah tentu nod akar adalah nilai minimum di antara mereka). Setiap kali terdapat input data, ia boleh dibandingkan dengan nod akar terlebih dahulu. Jika ia tidak lebih besar daripada nod akar, buang ia jika tidak, gantikan nilai nod akar dengan nilai baharu. Dan laraskan timbunan minimum.

Memandangkan hanya keping K data disimpan, kerumitan masa timbunan minimum dilaraskan kepada O(logK), jadi kerumitan masa bagi algoritma TOP K (masalah) ialah O(nlogK).

Answer 3

Cukup cari
http://www.cnblogs.com/skywang12345/p/3610187.html

Untuk bukti dan terbitan, lihat Pengenalan kepada Algoritma

Tetapi anda tidak perlu mengumpulnya, lagipun, anda hanya mencari 3 nombor...

Answer 4

Bukankah ini soalan Top K biasa Anda boleh mencari Top K di Baidu

Answer 5

Jawapan topn betul jika bertindan Soalan diambil dari 3 ini. . . Jumlah yang begitu kecil

Answer 6

Ia adalah jenis timbunan

Answer 7

penyelesaian topk

Answer 8

Jika anda mahu menjadi terpantas, saya rasa pengisihan bitmap adalah yang terpantas pernah saya lihat.