Temuduga Pengekodan: Mencari Elemen Ke-K Terbesar dalam Suatu Tatasusunan

Gesaan dan Konteks yang Berkenaan

Diberikan satu tatasusunan integer nums dan satu integer k, kembalikan elemen ke-k terbesar dalam susunan terisih, bukan nilai unik (distinct) ke-k. Andaikan 1 <= k <= nums.length <= 100,000 dan -10,000 <= nums[i] <= 10,000.

Sebagai contoh, nums = [3, 2, 1, 5, 6, 4] dan k = 2 mengembalikan 5. Untuk nums = [3, 2, 3, 1, 2, 4, 5, 5, 6] dan k = 4, jawapannya ialah 4: nilai pendua menduduki kedudukan pangkat yang berasingan.

Ini adalah masalah statistik tertib (order-statistics) yang representatif dalam temuduga pengekodan. Isihan penuh, min-heap bersaiz k, dan quickselect semuanya sah di bawah kekangan yang berbeza. Jawapan utama di bawah menggunakan randomized three-way quickselect kerana input ialah tatasusunan boleh ubah (mutable) dalam ingatan dan hanya satu kedudukan pangkat yang diperlukan. Ia mengubah nums; salin tatasusunan terlebih dahulu jika pemanggil memerlukan pemeliharaan input.

Perkara yang Dinilai oleh Penemuduga

Isyarat pertama ialah ketepatan kontrak. “Ke-k terbesar” bermaksud kedudukan k dalam susunan terisih menurun, termasuk nilai pendua. Ia tidak bermaksud nilai unik ke-k, k nilai terbesar, atau indeks k dalam tatasusunan berasaskan sifar. Dalam susunan menaik, elemen yang diminta mempunyai indeks berasaskan sifar n - k.

Isyarat kedua ialah sama ada calon menerbitkan alternatif dan bukannya sekadar menghafal quickselect. Pengisihan adalah garis dasar paling selamat pada O(n log n). Min-heap bersaiz k mengambil masa O(n log k) dan ruang O(k) serta berfungsi untuk input penstriman (streaming). Quickselect membuang pemetakan yang tidak mengandungi sasaran dan mempunyai jangkaan masa O(n), tetapi pemusatan rawak (randomized pivoting) tidak menghapuskan kes terburuk O(n^2).

Isyarat ketiga ialah penyataan invarian pemetakan. Kod yang sekadar “kelihatan seperti quicksort” tidak mencukupi. Calon sepatutnya dapat menyatakan apa yang diketahui tentang elemen sebelum lt, antara lt dan i, antara i dan gt, dan selepas gt, kemudian menerangkan sebab selang carian seterusnya masih mengandungi pangkat sasaran.

Akhir sekali, penemuduga mencari pengendalian nilai pendua, pendedahan mutasi input, tingkah laku input tidak sah, kawalan lelaran untuk mengelakkan risiko kedalaman rekursi, dan ujian yang membandingkan hasil dengan oracle mudah. Algoritma yang dioptimumkan tanpa sempadan bukti atau ujian adversarial adalah tidak lengkap.

Soalan untuk Dijelaskan Sebelum Menjawab

• Adakah ke-k terbesar mengira nilai pendua? Jawapan ini mengikut kedudukan terisih, jadi [5, 5, 4] dengan k = 2 mengembalikan 5. Keperluan pangkat unik (distinct) memerlukan penyahduplikasian atau pemilihan berasaskan kekerapan.
• Adakah k dijamin sah, dan bolehkah tatasusunan kosong? Kontrak temuduga yang dinyatakan menjamin 1 <= k <= n. Pelaksanaan masih mencetuskan ValueError di luar julat tersebut supaya tingkah laku kendirinya jelas.
• Bolehkah fungsi mengubah suai input? Pemetakan di tempat (in-place) memberikan ruang bantuan O(1). Jika pengubahsuaian dilarang, salin dahulu dan terima ruang tambahan O(n).
• Adakah input tersedia sepenuhnya atau berbentuk penstriman? Quickselect memerlukan capaian rawak (random access) dan mutasi. Untuk strim tanpa batas, kekalkan min-heap bersaiz k sebagai ganti.
• Adakah kita memerlukan satu pertanyaan atau banyak pertanyaan pangkat pada data yang sama? Quickselect menarik untuk satu pangkat. Mengisih sekali boleh menjadi lebih baik apabila banyak pertanyaan kemudian mewajarkan kerja awal O(n log n).
• Adakah julat nilai benar-benar kecil dan tetap? Julat yang dinyatakan hanya mempunyai 20,001 kemungkinan nilai integer, jadi pengiraan (counting) adalah alternatif yang sah. Ia mengambil masa O(n + R) dan ruang O(R) untuk lebar julat R, tetapi tidak boleh dibentangkan sebagai penyelesaian umum apabila nilai tidak terikat.
• Adakah masa kes terburuk mesti dibatasi? Randomized quickselect memberikan jangkaan masa linear, bukan masa linear kes terburuk berketentuan. Jika jaminan kes terburuk yang ketat diperlukan, bincangkan median-of-medians atau pilih heap dengan masa O(n log k) yang boleh diramal.

Rangka Kerja Jawapan 30 Saat

“Elemen ke-k terbesar ialah item pada indeks menaik n - k, dengan nilai pendua dikira. Pengisihan memberikan garis dasar O(n log n) yang mudah, dan min-heap bersaiz k memberikan masa O(n log k) untuk input penstriman atau bukan mutasi. Oleh kerana masalah ini meminta satu pangkat dalam tatasusunan boleh ubah dalam ingatan, saya akan menggunakan randomized quickselect berlelaran. Saya memetakkan selang aktif kepada nilai yang lebih kecil daripada, sama dengan, dan lebih besar daripada pangsi (pivot) rawak. Jika n - k berada dalam jalur yang sama, pangsi tersebut ialah jawapannya; jika tidak, saya hanya menyimpan bahagian yang mengandungi indeks tersebut. Pemetakan three-way mengelakkan pemprosesan berulang nilai yang sama. Jangkaan masa ialah O(n), kes terburuk O(n^2), dan ruang bantuan ialah O(1). Saya akan mengesahkannya terhadap pengisihan pada tatasusunan rawak ditambah dengan kes semua-sama, terisih, terisih-terbalik, padat pendua, dan sempadan-k.”

Jawapan Mendalam Langkah demi Langkah

Mulakan dengan sebuah oracle. Mengisih secara menaik dan mengembalikan sorted(nums)[len(nums) - k] adalah mudah untuk diterangkan dan sukar untuk silap. Ia menetapkan penukaran pangkat dan menyediakan hasil rujukan untuk ujian. Kosnya ialah masa O(n log n) dan ruang O(n) apabila memelihara input asal dengan salinan.

Bounded heap menambah baik kerja apabila k kecil atau data tiba secara berperingkat. Masukkan setiap nilai ke dalam min-heap dan keluarkan minimum setiap kali saiznya melebihi k. Selepas semua nilai selesai, punca (root) ialah nilai terkecil antara k elemen terbesar, oleh itu ia adalah elemen ke-k terbesar. Heap menyimpan k nilai, jadi kosnya ialah masa O(n log k) dan ruang O(k). Jika k mendekati n dan keseluruhan tatasusunan sudah tersedia, kelebihan ini berkurangan.

Quickselect menggunakan fakta bahawa hanya satu kedudukan akhir yang penting. Tukar pangkat menurun kepada target = len(nums) - k. Dalam setiap selang aktif [left, right], pilih nilai pangsi rawak dan lakukan pemetakan Dutch national flag. Semasa imbasan, kekalkan:

• [left, lt) mengandungi nilai yang lebih kecil daripada pangsi.
• [lt, i) mengandungi nilai yang sama dengan pangsi.
• [i, gt] belum dikelaskan.
• (gt, right] mengandungi nilai yang lebih besar daripada pangsi.

Apabila imbasan tamat, [lt, gt] ialah jalur lengkap nilai yang sama. Jika target < lt, teruskan di bahagian nilai lebih kecil. Jika target > gt, teruskan di bahagian nilai lebih besar. Jika tidak, sasaran berada di dalam jalur yang sama, maka nilai pangsi adalah jawapannya. Pengendalian ini penting untuk tatasusunan seperti [7, 7, 7, 7]: pemetakan two-way boleh menghasilkan kerja yang hampir tidak berubah secara berulang, manakala versi three-way selesai selepas satu imbasan.

import random


def find_kth_largest(nums: list[int], k: int) -> int:
    if not 1 <= k <= len(nums):
        raise ValueError("k must be between 1 and len(nums)")

    target = len(nums) - k
    left = 0
    right = len(nums) - 1

    while left <= right:
        pivot = nums[random.randrange(left, right + 1)]
        lt = left
        i = left
        gt = right

        while i <= gt:
            if nums[i] < pivot:
                nums[lt], nums[i] = nums[i], nums[lt]
                lt += 1
                i += 1
            elif nums[i] > pivot:
                nums[i], nums[gt] = nums[gt], nums[i]
                gt -= 1
            else:
                i += 1

        if target < lt:
            right = lt - 1
        elif target > gt:
            left = gt + 1
        else:
            return pivot

    raise RuntimeError("unreachable for a valid k")

Peningkatan i sengaja dibuat tidak simetri. Selepas menukar nilai yang lebih besar daripada pangsi dengan nums[gt], nilai baharu di i belum dikelaskan, jadi i kekal di tempatnya. Selepas memindahkan nilai yang lebih kecil ke kiri, kedua-dua kedudukan yang ditukar mempunyai klasifikasi yang diketahui, jadi kedua-dua lt dan i mara ke hadapan.

Ketepatan algoritma berpunca daripada invarian dan penyingkiran pangkat. Pemetakan memelihara setiap elemen input dan berakhir dengan semua nilai yang lebih kecil sebelum jalur sama dan semua nilai yang lebih besar selepasnya. Oleh itu, setiap indeks dalam [lt, gt] mempunyai nilai pangsi dalam susunan terisih. Jika sasaran berada di luar jalur tersebut, bahagian yang dibuang dan jalur sama tidak mengandungi elemen yang boleh menduduki indeks sasaran; selang yang disimpan masih mengandunginya. Setiap lelaran sama ada mengembalikan hasil atau memendekkan selang secara ketat, jadi sasaran yang sah akhirnya akan dikembalikan.

Setiap pemetakan mengimbas selang semasa sekali. Dengan pangsi rawak, jangkaan jumlah kerja ke atas selang yang disimpan secara berturut-turut ialah O(n). Urutan pangsi yang sentiasa melampau (extreme) boleh meninggalkan selang bersaiz n - 1, n - 2, dan seterusnya, menghasilkan masa kes terburuk O(n^2). Pelaksanaan ini berlelaran dan memetakkan di tempat (in-place), jadi ruang bantuannya ialah O(1). Keadaan penjana nombor rawak dan tatasusunan input itu sendiri tidak dikira sebagai storan bantuan.

Uji dengan oracle terisih yang mudah dan bukan hanya contoh tetap:

def oracle(nums: list[int], k: int) -> int:
    return sorted(nums)[len(nums) - k]


cases = [
    ([3, 2, 1, 5, 6, 4], 2),
    ([3, 2, 3, 1, 2, 4, 5, 5, 6], 4),
    ([1], 1),
    ([7, 7, 7, 7], 3),
    ([-5, -1, -3, -1], 2),
    (list(range(1000)), 1),
    (list(range(1000)), 1000),
]

for values, rank in cases:
    assert find_kth_largest(values.copy(), rank) == oracle(values, rank)

Tambah tatasusunan yang dijana dengan banyak nilai pendua dan bandingkan setiap k yang sah dengan oracle. Sahkan juga bahawa k = 0, k > n, dan tatasusunan kosong mencetuskan ralat yang didokumenkan. Menetapkan benih (seed) pada penjana rawak menjadikan ujian sifat yang gagal boleh dihasilkan semula; menjalankan pelbagai benih menguji laluan pemetakan yang berbeza.

Contoh Jawapan Berkualiti Tinggi

“Saya akan menganggap nilai pendua sebagai kedudukan terisih yang berasingan dan mengandaikan k adalah sah. Jika tatasusunan diisih secara menaik, jawapannya adalah pada indeks n - k. Garis dasar saya adalah untuk mengisih dan mengindeks, iaitu O(n log n). Min-heap bersaiz k ialah O(n log k) dan akan menjadi pilihan saya untuk data penstriman.

Di sini kita mempunyai satu pertanyaan dan boleh mengubah tatasusunan, jadi saya akan menggunakan randomized quickselect. Dalam julat aktif, saya memilih pangsi rawak dan membahagikan nilai kepada kurang daripada, sama dengan, dan lebih besar daripada pangsi. Pembahagian three-way adalah penting kerana nilai pendua harus menduduki beberapa kedudukan pangkat dan input yang semuanya sama harus selesai dalam satu pemetakan. Selepas pemetakan, jika n - k berada dalam julat yang sama, saya kembalikan pangsi. Jika tidak, saya buang bahagian yang tidak boleh mengandungi indeks tersebut dan ulangi secara berlelaran.

Invariannya ialah semua elemen sebelum lt adalah lebih kecil, semua elemen daripada lt hingga i adalah sama, semua elemen selepas gt adalah lebih besar, dan bahagian tengah yang tidak diketahui masih belum dikelaskan. Ini membuktikan jalur sama yang terakhir mempunyai selang pangkat terisih yang betul. Oleh itu, bahagian yang disimpan masih mengandungi jawapannya.

Jangkaan masa jalanan ialah O(n) kerana pangsi rawak biasanya membuang sebahagian besar data, walaupun kes terburuk kekal O(n^2). Gelung dan pemetakan di tempat menggunakan ruang bantuan O(1). Saya akan mendedahkan bahawa fungsi ini mengubah inputnya, membandingkannya dengan oracle pengisihan pada tatasusunan yang dijana, dan menyertakan kes pendua, data semua-sama, tatasusunan terisih dan terisih-terbalik, nilai negatif, k = 1, dan k = n.”

Kesilapan Biasa

• Mengembalikan nilai unik (distinct) ke-k → nilai pendua adalah kedudukan berasingan dalam kontrak → Tukar terus kepada indeks menaik n - k tanpa menyahduplikasi.
• Menggunakan indeks k atau k - 1 dalam susunan menaik → penukaran arah adalah salah → Semak bahawa k = 1 memetakan kepada n - 1 dan k = n memetakan kepada 0.
• Mendakwa penyelesaian min-heap ialah O(n log n) → heap tidak pernah melebihi elemen k → Nyatakan masa O(n log k) dan ruang O(k).
• Melakukan rekursi ke dalam kedua-dua pemetakan → itu melakukan kerja quicksort dan mengabaikan matlamat pangkat tunggal → Teruskan hanya dalam selang yang mengandungi target.
• Sentiasa memilih pangsi pertama atau terakhir → input yang terisih atau direka khusus boleh berulang kali mencipta selang bersaiz n - 1 → Rawakkan pangsi dan kekalkan kaveat kes terburuk.
• Menggunakan pemetakan two-way tanpa membincangkan nilai pendua → tatasusunan yang sarat dengan nilai sama boleh menghasilkan kemajuan yang lemah → Cipta satu jalur sama dan kembalikan apabila sasaran berada di dalamnya.
• Meningkatkan i selepas menukar dengan gt → nilai baharu yang masuk masih belum dikelaskan dan mungkin terlepas → Kekalkan i sehingga nilai tersebut dikelaskan.
• Mendakwa perawakan menjamin masa linear → pangsi yang tidak bernasib baik masih wujud → Katakan jangkaan O(n), kes terburuk O(n^2).
• Menyembunyikan mutasi input → pemanggil mungkin bergantung pada susunan asal → Nyatakan kontrak mutasi atau salin dan peruntukkan ruang O(n).
• Hanya menguji dua contoh → pepijat off-by-one, pendua, dan pemetakan kekal tersembunyi → Bandingkan terhadap pengisihan merentas sempadan, kes berstruktur, dan input yang dijana.

Soalan Susulan dan Cara Mengendalikannya

Susulan 1: Apakah yang berubah jika input ialah strim tanpa batas?

Quickselect tidak lagi sesuai kerana tatasusunan capaian rawak yang lengkap tidak wujud. Kekalkan min-heap dengan paling banyak k nilai. Tolak elemen sehingga mencapai k; selepas itu gantikan punca hanya apabila nilai yang lebih besar tiba. Punca ialah nilai ke-k terbesar yang dilihat setakat ini. Kemas kini mengambil kos O(log k), pertanyaan mengambil kos O(1), dan memori ialah O(k). Jika k itu sendiri berubah secara sewenang-wenangnya, keadaan ini mungkin tidak mencukupi dan kontrak memerlukan struktur tertib yang lebih kaya atau pengekalan data.

Susulan 2: Bagaimana jika fungsi mesti memelihara input?

Penyesuaian paling mudah ialah working = nums.copy() dan quickselect pada working, mengubah ruang bantuan kepada O(n). Heap bersaiz k memelihara input dengan ruang O(k) dan mungkin lebih baik apabila k adalah kecil. Pengisihan penuh bagi salinan adalah lebih mudah apabila n sederhana atau banyak pertanyaan pangkat akan menggunakan semula hasil terisih tersebut.

Susulan 3: Bolehkah anda menjamin masa linear kes terburuk?

Median-of-medians memilih pangsi yang membuang pecahan malar dalam kes terburuk, memberikan pemilihan O(n) berketentuan. Pelaksanaan dan pemalar nilainya lebih besar, jadi randomized quickselect selalunya merupakan pilihan praktikal dalam temuduga melainkan keperluan secara eksplisit menuntut batas kes terburuk. Bounded heap menawarkan alternatif O(n log k) yang lebih mudah dan boleh diramal.

Susulan 4: Bagaimanakah anda menggunakan julat integer yang kecil?

Cipta tatasusunan kekerapan untuk nilai dari -10,000 hingga 10,000, imbas nums, kemudian susuri kekerapan daripada tinggi ke rendah sambil menolak kiraan daripada k. Baldi (bucket) pertama yang mengandungi baki pangkat ialah jawapannya. Dengan lebar julat R = 20,001, ini mengambil masa O(n + R) dan ruang O(R). Ia adalah berketentuan dan mengendalikan nilai pendua secara semula jadi, tetapi ia menjadi tidak sesuai apabila julat adalah besar atau tidak terikat.

Susulan 5: Bagaimana jika penemuduga meminta k elemen terbesar, dalam susunan terisih?

Satu order statistic bukan lagi keseluruhan output. Heap bersaiz k diikuti dengan pengisihan heap mengambil masa O(n log k + k log k) dan ruang O(k). Quickselect boleh memetakkan sekitar pangkat n - k, selepas itu mengisih nilai k terpilih mengambil jangkaan masa O(n + k log k). Buat pilihan berdasarkan mutasi, memori, keperluan kes terburuk, dan sama ada susunan output diperlukan.

Susulan 6: Bagaimanakah anda membuat kegagalan ujian rawak boleh dihasilkan semula?

Terima suntikan penjana nombor rawak atau letakkan benih (seed) pada penjana sebelum setiap ujian. Rekod benih, input, dan k semasa kegagalan. Jalankan input yang sama merentas beberapa benih tetap, dan bandingkan setiap jawapan dengan oracle pengisihan. Ini memisahkan ralat algoritma daripada laluan pangsi tertentu sambil mengekalkan kebolehulangan dalam integrasi berterusan (continuous integration).