javascript - Cari median integer 10G, had memori ialah 2G.

Question

Tencent mempunyai soalan pengambilan sekolah sedemikian:
Untuk PC dengan hanya 2G memori, cari median dalam fail yang mengandungi 10G integer dan tulis algoritma.

Terdapat beberapa penyelesaian, seperti pengisihan baldi dan pengisihan radix, tetapi saya menemui kaedah yang menggunakan timbunan untuk menyelesaikannya. Saya tidak begitu memahaminya 1G terbesar, dan kemudian Gunakan elemen ini untuk mencari 2G terbesar, dan kemudian gunakan 2G terbesar untuk mencari 3G terbesar... Sudah tentu, walaupun ini tidak memerlukan pengisihan, akan terdapat lebih banyak operasi cakera, dan yang khusus perlu dianalisis. Antara pengisihan bawah dan luar yang manakah akan mempunyai lebih banyak IO cakera?
Buat timbunan maksimum 1g integer Jika elemen itu kurang daripada nilai maksimum, masukkannya ke dalam timbunan Dengan cara ini, anda boleh mendapatkan 1gth elemen terbesar dan kemudian gunakan elemen ini untuk membina semula timbunan sekali, dan tambah elemen ke-1 terbesar lebih besar daripada syarat untuk memasuki timbunan kali ini, supaya selepas membina timbunan, anda boleh mendapatkan elemen ke-2 terbesar.

Saya keliru apabila saya melihatnya Pertama, saya tidak faham apa itu 1G Adakah untuk membahagikan data 10G kepada 10 bahagian, dan kemudian mengisih data 1G untuk mencari makna terbesar?
Saya harap anda boleh memberi saya beberapa idea untuk penyelesaian ini, terima kasih.

Answer 1

Timbunan ialah struktur data, iaitu pokok binari yang lengkap (jadi tiada penuding diperlukan untuk menyimpan strukturnya setiap nod tidak lebih besar daripada atau tidak lebih kecil daripada nod anaknya, sepadan dengan timbunan atas yang besar dan timbunan atas yang kecil). masing-masing. Sebagai contoh, dalam timbunan atas yang kecil, unsur akar adalah yang terkecil. Jadi ia boleh digunakan sebagai O(1)的复杂度查找其中的最大或是最小的元素。其删除和插入元素的复杂度，最坏情况下都是O(log(N)).

Petikan ini bermakna dengan mula-mula mencipta timbunan atas kecil yang boleh menampung data (1G+1), anda boleh mencari elemen terkecil di dalamnya dengan cepat. Kemudian lintasi semua 10G data dan masukkannya: jika timbunan penuh selepas sisipan (terdapat data 1G+1 dalam timbunan). Hanya padamkan yang terkecil. . . .
Hasil akhir ialah data dalam timbunan adalah data 1G terbesar, dan bahagian atas timbunan adalah yang terkecil, iaitu, jika diisih dalam tertib menurun, kedudukan data ini ialah kedudukan 1G, contohnya, nombor ini ialah x.
Kemudian, teruskan proses di atas sekali lagi, tetapi perbezaannya ialah hanya elemen yang kurang daripada x dimasukkan ke dalam timbunan, dan elemen yang lebih besar daripada atau sama dengan x diabaikan. Iaitu, selepas mengabaikan data 1G yang baru ditemui, cari 1G terbesar. Dengan cara ini, bahagian atas timbunan terakhir ialah data pada kedudukan 2G selepas mengisih. (Tetapi berhati-hati apabila berurusan dengan data pendua). . . . Dan seterusnya untuk mencari median.

Answer 2

Saya ada soalan, bukankah soalan seperti ini boleh dilakukan menggunakan peta bit? . .
1. Lintas nombor 10G ini, tandakan yang mana yang telah muncul dalam bitmap, dan hitung berapa banyak nombor berbeza yang telah muncul, rekodkannya sebagai kiraan
2. Lintas bitmap, cari kiraan/bit ke-2, iaitu nombor ini. . .

Jika integer ialah 4bait seperti 0 ~ 2^32-1. Kemudian untuk menyimpan julat nilainya, anda hanya memerlukan bitmap memori 512M. . . . ?

Answer 3

Saya masih mempunyai beberapa soalan yang berbeza tentang kaedah ini Jika pakar mendapati ia menarik, anda boleh lihat:
Oleh kerana ia dibahagikan kepada 10 timbunan, apakah nilai sempadan sepunya bagi setiap timbunan?

Jika dibahagikan kepada sepuluh longgokan, berapa banyak penghakiman yang diperlukan untuk mengisih pantas dalam kes terburuk?

Adakah mungkin untuk mengurangkan jumlah pengiraan?

@zonxin