Kth Largest Element in a Stream

Q: Mengapa menggunakan min-heap, bukan max-heap, untuk mencari elemen terbesar ke-k?

Nilai terkecil dari k nilai terbesar adalah jawabannya sekaligus nilai yang harus dilampaui oleh nilai baru, dan min-heap berukuran k menjaga nilai tersebut tetap di puncak. Max-heap yang berisi setiap nilai menempatkan nilai terbesar di puncak, jadi untuk mencapai nilai ke- k , kamu harus mengeluarkan k-1 nilai lalu memasukkannya kembali setiap kali ada nilai baru.

Q: Berapa kompleksitas waktu untuk Elemen Terbesar ke-K dalam Stream?

Setiap elemen yang masuk membutuhkan O(log k) : satu perbandingan dengan elemen teratas dan paling banyak satu proses sift melalui heap yang berisi k nilai. Membangun heap dari nums membutuhkan O(n log k) , jadi seluruh proses memerlukan waktu O((n + m) log k) dan ruang tambahan O(k) .

MudahHeap

+10

Aliran bilangan bulat dimulai dengan nilai-nilai dalam nums. Kemudian, nilai-nilai dari adds tiba satu per satu. Setelah setiap nilai tiba, catat nilai terbesar ke-k dari semua nilai yang telah dilihat sejauh ini, dengan menghitung nilai yang sama secara terpisah. Kembalikan nilai-nilai yang dicatat sesuai urutannya, satu untuk setiap nilai dalam adds.

nums berisi setidaknya k-1 nilai, jadi setelah nilai pertama tiba, selalu ada setidaknya k nilai yang dapat dipilih.

Fungsi

kthLargestStream(k: integer, nums: integer-array, adds: integer-array) → integer-array

kinteger: peringkat yang akan dilaporkan, 1 untuk nilai terbesar
numsinteger-array: nilai yang sudah ada di dalam aliran
addsinteger-array: nilai-nilai yang tiba, secara berurutan
Mengembalikaninteger-array: nilai terbesar ke-k setelah setiap kedatangan

Batasan

1 ≤ nums.length ≤ 10⁴
1 ≤ adds.length ≤ 10⁴
1 ≤ k ≤ nums.length + 1
-10⁴ ≤ nums[i], adds[i] ≤ 10⁴
nums boleh dalam urutan apa pun, dan nilai yang sama dihitung sebagai nilai terpisah.

Contoh

Input: k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
Output: [3, 5, 6, 6, 7]
Penjelasan: Setelah 3, nilai terbesar ketiga dari 7, 5, 3, dan 1 adalah 3. Lalu 9 menaikkannya menjadi 5, 6 menaikkannya menjadi 6, 2 tidak mengubah apa pun, dan 8 menaikkannya menjadi 7 (9, 8, 7).

Input: k = 1nums = [-2]adds = [-5, 0, -1, 4]
Output: [-2, 0, 0, 4]
Penjelasan: Dengan k = 1, jawabannya adalah nilai terbesar sejauh ini: -2 sampai 0 muncul, tetap 0 setelah -1, lalu 4.

Pertanyaan lanjutan

Bagaimana kamu akan menjawab pertanyaan yang sama jika nilai juga bisa dihapus dari aliran?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Nilai tidak pernah keluar dari aliran, jadi nilai yang lebih kecil daripada nilai terbesar ke-k saat ini tidak akan masuk lagi. Simpan hanya k nilai terbesar dalam min-heap: elemen teratasnya adalah jawabannya, dan setiap nilai yang masuk memerlukan satu perbandingan serta paling banyak satu pembaruan heap berbiaya O(log k).

Urutkan setiap selesai kedatangan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Simpan setiap nilai dalam sebuah list. Setelah setiap kedatangan, urutkan list tersebut secara menaik dan baca indeks length-k, yaitu nilai terbesar ke-k berdasarkan definisi.

Setiap kedatangan mengurutkan hingga n + m nilai, dengan n dan m sebagai panjang nums dan adds. Jika masing-masing berisi 10^4 nilai, jumlahnya sekitar 2 × 10^9 perbandingan.

Algoritma

Salin nums ke dalam list values.
Untuk setiap nilai adds, tambahkan nilai itu ke values.
Urutkan values dari yang terkecil ke terbesar, lalu catat values[length-k].
Kembalikan nilai yang dicatat.

def kthLargestStream(k, nums, adds):
    values = list(nums)
    result = []
    for x in adds:
        values.append(x)
        values.sort()
        # In increasing order the k-th largest sits k places from the end.
        result.append(values[len(values) - k])
    return result

Min-heap dari k nilai terbesar

Intuisi

Setelah sebuah nilai memiliki k nilai yang lebih besar di atasnya, hal itu tetap benar untuk sisa aliran data, jadi hanya k nilai terbesar yang sejauh ini ditemukan yang penting. Simpan nilai-nilai itu dalam min-heap. Elemen teratasnya adalah yang terkecil di antara k nilai terbesar, tepatnya nilai terbesar ke-k secara keseluruhan.

Ketika x tiba dan heap sudah penuh, bandingkan dengan elemen teratas. Jika x tidak lebih besar, nilainya bukan termasuk k nilai terbesar dan tidak ada yang berubah. Jika lebih besar, elemen teratas dikeluarkan: ganti dengan x lalu lakukan sift down, dalam O(log k). Nilai-nilai awal juga melalui proses yang sama, jadi nums bisa lebih panjang dari k.

Dalam contoh pertama, heap berisi 7, 1, dan 5 setelah nums, dengan 1 di posisi teratas. Nilai 3 yang tiba menggantikan 1, dan elemen teratas, 3, menjadi jawaban pertama.

Algoritma

Mulai dengan min-heap kosong.
Untuk menambahkan x: jika heap berisi kurang dari k nilai, masukkan x. Jika tidak, dan x lebih besar dari nilai teratas, ganti nilai teratas dengan x dan pulihkan urutan heap.
Tambahkan setiap nilai nums dengan cara ini.
Untuk setiap nilai adds, tambahkan nilai itu dan catat nilai teratas heap.
Kembalikan nilai-nilai yang dicatat.

import heapq


def kthLargestStream(k, nums, adds):
    # A min-heap of the k largest values so far; heap[0] is the smallest of them.
    heap = []

    def add(x):
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x

    for x in nums:
        add(x)
    result = []
    for x in adds:
        add(x)
        result.append(heap[0])  # the k-th largest so far
    return result

Jebakan dan kasus tepi

Menghapus duplikat. Empat nilai terbesar dari 9, 6, 6, 6, 2 adalah 9, 6, 6, dan 6. Set, atau pemeriksaan yang melewati nilai yang sudah ada, menghasilkan 2 pada contoh ketiga, bukan 6.
Membaca jawaban sebelum menambahkan. Saat nums berisi k-1 nilai, heap baru penuh setelah nilai pertama masuk. Jadi, tambahkan nilai terlebih dahulu, lalu baca nilai teratas.
Menghitung dari ujung yang salah setelah pengurutan. Dalam urutan menaik, nilai terbesar ke-k ada di indeks length-k; indeks k-1 berisi nilai terkecil ke-k.
Menggunakan urutan heap default. priority_queue milik C++ dan BinaryHeap milik Rust adalah max-heap: berikan greater<int> atau bungkus nilai dengan Reverse.

Pertanyaan yang sering diajukan3

Mengapa menggunakan min-heap, bukan max-heap, untuk mencari elemen terbesar ke-k?

Nilai terkecil dari k nilai terbesar adalah jawabannya sekaligus nilai yang harus dilampaui oleh nilai baru, dan min-heap berukuran k menjaga nilai tersebut tetap di puncak. Max-heap yang berisi setiap nilai menempatkan nilai terbesar di puncak, jadi untuk mencapai nilai ke-k, kamu harus mengeluarkan k-1 nilai lalu memasukkannya kembali setiap kali ada nilai baru.

Berapa kompleksitas waktu untuk Elemen Terbesar ke-K dalam Stream?

Setiap elemen yang masuk membutuhkan O(log k): satu perbandingan dengan elemen teratas dan paling banyak satu proses sift melalui heap yang berisi k nilai. Membangun heap dari nums membutuhkan O(n log k), jadi seluruh proses memerlukan waktu O((n + m) log k) dan ruang tambahan O(k).

Bisakah Kth Largest Element in a Stream diselesaikan dengan list yang diurutkan?

Ya. Jaga agar semua nilai tetap terurut, sisipkan setiap nilai yang datang pada posisinya menggunakan pencarian biner, lalu baca nilai k posisi dari akhir. Pencariannya membutuhkan O(log n), tetapi menggeser nilai setelah titik penyisipan membutuhkan O(n) untuk setiap nilai yang datang: sekitar 1.5 × 10^8 pergeseran untuk 10^4 nilai awal dan 10^4 nilai yang datang.

def kthLargestStream(k, nums, adds):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

k = 3
nums = [7, 1, 5]
adds = [3, 9, 6, 2, 8]

Output yang diharapkan

[3, 5, 6, 6, 7]