Temu Duga Pengekodan: Gunakan Quickselect untuk Mencari Unsur Terbesar ke-K dengan Duplikasi

Soalan dan skop

Diberikan satu tatasusunan integer yang tidak tersusun nums dan 1 ≤ k ≤ nums.length, kembalikan unsur ke-k dalam susunan tidak menaik. Nilai duplikasi menduduki kedudukan yang berasingan: nilai kedua terbesar dalam [5, 5, 4] ialah 5, bukannya nilai unik kedua. Sasaran masa purata ialah O(n) dengan ruang tambahan O(1) apabila pengubahsuaian tatasusunan dibenarkan; nyatakan andaian tersebut sebelum mula mengekod.

Perkara yang diuji oleh penemu duga

Jawapan yang kukuh memetakan "terbesar ke-k" kepada indeks menaik target = n-k, kemudian menjelaskan bahawa pembahagian hanya perlu membina sempadan di sekeliling pivot; bahagian yang satu lagi tidak perlu diisih sama sekali. Ia mengendalikan nilai duplikasi, k=1, k=n, input yang tersusun, serta perbezaan antara kerumitan purata rawak dan jaminan kes terburuk.

Penjelasan sebelum mengekod

1. Bolehkah input diubah suai? Pembahagian setempat (in-place) menggunakan ruang tambahan O(1); mengekalkannya memerlukan salinan O(n).
2. Adakah ini kedudukan ke-k atau nilai unik ke-k? Pengiraan kedudukan ialah penyataan lazim; pemilihan nilai unik memerlukan pengendalian nilai duplikasi yang berbeza.
3. Adakah data tiba sebagai strim? Quickselect adalah untuk satu tatasusunan yang diwujudkan; min-heap bersaiz k memberikan pemprosesan O(n log k) bagi sesuatu strim.
4. Adakah batas kes terburuk yang deterministik diwajibkan? Quickselect rawak mempunyai purata O(n); median-daripada-median atau jaminan pustaka diperlukan untuk tuntutan kes terburuk yang ketat.

Penyelesaian yang disyorkan dan derivasi

Gunakan pembahagian tiga hala kepada nilai yang lebih kecil daripada, sama dengan, dan lebih besar daripada pivot. Untuk indeks menaik yang telah ditukar target, teruskan dengan selang kiri apabila sasaran berada di sebelah kiri lt, selang kanan apabila ia berada di sebelah kanan gt, dan kembalikan pivot apabila ia berada dalam [lt, gt]. Jalur nilai sama membolehkan input yang kesemuanya bernilai sama selesai dalam satu imbasan dan bukannya membuang satu item secara berulang kali.

import random

def kth_largest(nums: list[int], k: int) -> int:
    if not 1 <= k <= len(nums):
        raise ValueError("k out of range")
    target = len(nums) - k
    left, right = 0, len(nums) - 1
    while left <= right:
        pivot = nums[random.randint(left, right)]
        lt, i, gt = left, left, 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")

Setiap lelaran mengimbas selang semasanya sekali. Jika pivot mengecilkan selang sebanyak pecahan malar, T(n)=T(cn)+O(n) menghasilkan purata O(n); memilih nilai ekstrem secara berulang masih menghasilkan O(n²) dalam kes terburuk. Bentuk lelaran mengelakkan kedalaman rekursi dan menggunakan ruang tambahan O(1).

Alternatif dan pertukaran kompromi

Pengisihan penuh adalah paling mudah untuk disahkan, memakan kos O(n log n), dan wajar digunakan apabila tatasusunan adalah kecil atau susunan yang lengkap diperlukan kemudian. Min-heap bersaiz k mengekalkan input dan memakan masa O(n log k) serta ruang O(k), yang sesuai untuk strim atau apabila k jauh lebih kecil daripada n. C++ std::nth_element mendedahkan semantik pembahagian yang sama dengan kerumitan purata linear; ia tidak mengisih mana-mana bahagian daripada kedudukan yang dipilih.

Mod kegagalan, sempadan, dan contoh lawan

• Menulis target = k-1 mencari nilai terkecil ke-k, menyongsangkan susunan yang diminta.
• Pembahagian dua hala yang hanya membuang satu item yang sama boleh mengambil masa O(n²) pada [7, 7, 7, ...]; pembahagian tiga hala memproses keseluruhan jalur nilai sama sekali gus.
• Sentiasa memilih unsur terakhir boleh merosot prestasinya pada input yang tersusun dan tersusun secara songsang. Perawakan mengurangkan kebarangkalian, bukan batas kes terburuk asimptotik.
• "Terbesar unik ke-k" tidak boleh menggunakan semula syarat henti tanpa mengira atau mengeluarkan jalur nilai sama.
• Tolak tatasusunan kosong, k=0, atau k>n pada sempadan dan bukannya membiarkan ralat indeks menyembunyikan soalan yang tidak sah.

Senarai semak ujian dan pengesahan

Bandingkan kes rawak dengan sorted(nums)[-k]; sertakan nilai yang semuanya sama, nombor negatif dan duplikasi, k=1, k=n, input tersusun, dan input tersusun secara songsang. Apabila pengubahsuaian dibenarkan, sahkan keputusannya dan bukannya keseluruhan susunan tatasusunan. Tetapkan benih rawak untuk kebolehulangan dan rekodkan bilangan perbandingan apabila n bertambah; satu larian yang bernasib baik bukanlah bukti kerumitan.

Soalan susulan

Bagaimanakah kes terburuk boleh dijamin linear?

Pilih pivot median-daripada-median supaya setiap pusingan mengeluarkan pecahan yang tetap, memberikan masa kes terburuk O(n). Pemalar baginya adalah lebih tinggi, jadi kod pengeluaran biasanya memilih pemilihan rawak atau pelaksanaan pustaka standard.

Bagaimanakah anda mengubahnya kepada nilai terkecil ke-k?

Gunakan target = k-1 sambil mengekalkan pembahagian menaik. Mengekalkan formulasi terbesar sebagai target=n-k selalunya lebih jelas daripada menyongsangkan tatasusunan.

Bagaimanakah anda menyokong operasi sisipan dan banyak pertanyaan pangkat?

Quickselect sekali laksana akan mengimbas semula pada setiap pertanyaan. Untuk satu nilai k yang tetap, kekalkan satu min-heap bersaiz k; untuk pertanyaan pangkat rawak, pertimbangkan pepohon seimbang yang ditambah dengan saiz subpokok dan pilih berdasarkan nisbah kemas kini kepada pertanyaan.