Temu duga pengekodan: Bagaimana anda mencari integer positif ke-k yang hilang dengan carian binari?

Perkara yang dinilai oleh penemu duga

Masalah di permukaan ialah mengira dalam tatasusunan; terasnya adalah mengubah "berapa banyak nilai yang hilang sehingga indeks i" menjadi predikat monotonik dan kemudian mencari sempadannya. LeetCode 1539 menyediakan pernyataan masalah awam dan entri set soalan Amazon. Panduan SDE Amazon menekankan kod yang boleh dijalankan, teguh, teruji dan pemeriksaan kes pinggir. Sumber-sumber ini menyokong nilai persediaan, bukan tuntutan kekerapan temu duga yang tetap untuk mana-mana syarikat.

• Sama ada anda menulis missing(i) = arr[i] - i - 1.
• Sama ada anda membuktikan bahawa kiraan yang hilang adalah tidak menurun (non-decreasing).
• Sama ada anda mengendalikan jawapan di luar elemen tatasusunan terakhir.
• Sama ada anda membandingkan pengimbasan, carian binari dan penjanaan langsung mengikut kontrak.

Rangka kerja jawapan 30 saat

Nyatakan bahawa tatasusunan menggunakan indeks berasaskan sifar. Sehingga arr[i], terdapat arr[i] integer positif dalam julat nilai tetapi hanya i + 1 elemen yang diperhatikan, jadi kiraan yang hilang ialah arr[i] - i - 1. Buat carian binari untuk indeks pertama dengan missing(i) >= k. Jika ia adalah i, jawapannya ialah k + i; jika tiada indeks yang memuaskannya, jawapannya adalah selepas tatasusunan dan merupakan k + n. Pengimbasan mengambil masa O(n), carian binari O(log n), dan kedua-duanya menggunakan ruang tambahan O(1).

Soalan penjelasan sebelum menjawab

1. Adakah tatasusunan dijamin meningkat secara tegas dan bernilai positif? Jika tidak, pengisihan atau penyahduplikasian mengubah kontrak.
2. Adakah k bernilai positif, dan bolehkah nilai melebihi julat integer selamat bahasa pengaturcaraan?
3. Adakah satu nilai diperlukan, atau semua nilai yang hilang? Mengembalikan semua nilai mempunyai kos output.
4. Bolehkah input distrim tanpa capaian rawak? Itu mungkin memihak kepada pengimbasan.
5. Adakah tatasusunan asal mesti kekal tidak berubah? Penyelesaian carian binari tidak mengubahnya.

Analisis mendalam langkah demi langkah

Langkah 1: Bina formula kiraan yang hilang

Jika tatasusunan adalah berterusan, arr[i] akan sama dengan i + 1. Perbezaannya ialah bilangan integer positif yang hilang daripada [1, arr[i]]:

missing(i) = arr[i] - (i + 1)
           = arr[i] - i - 1

Untuk arr = [2, 3, 4, 7, 11] dan i=3, missing(3) = 7 - 3 - 1 = 3; nilai yang hilang ialah 1, 5, dan 6.

Langkah 2: Gunakan kemonotonan untuk sempadan

Peningkatan tegas menghasilkan arr[i+1] >= arr[i] + 1. Oleh itu missing(i+1) >= missing(i), jadi kiraan tidak pernah berkurang. Cari indeks pertama dengan missing(i) >= k: semua sebelum ini mempunyai nilai hilang yang terlalu sedikit, manakala indeks tersebut dan semua selepasnya mempunyai sekurang-kurangnya k.

Langkah 3: Dapatkan semula jawapan daripada sempadan

Katakan sempadan ialah i. Terdapat i elemen tatasusunan yang diperhatikan sebelumnya, dan kurang daripada k nilai yang hilang sebelum sempadan. Oleh itu, nilai hilang ke-k ialah k + i. Jika tiada sempadan wujud, kiraan hilang akhir masih di bawah k; kesemua n elemen yang diperhatikan terletak sebelum jawapan, jadi hasilnya ialah k + n.

Langkah 4: Laksanakan carian binari

function findKthPositive(arr: number[], k: number): number {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    const missing = arr[mid] - mid - 1;
    if (missing < k) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return k + left;
}

Menggunakan right = n membolehkan sempadan berada tepat selepas tatasusunan. Pada penamatan, left ialah kedudukan pertama yang kiraan hilangnya mencapai k, jadi formula k + left yang sama mengendalikan kedua-dua kes.

Langkah 5: Buktikan kerumitan dan uji sempadan

Setiap lelaran membahagi dua selang carian, memberikan masa O(log n) dan pemboleh ubah tambahan malar. Uji arr = [1,2,3,4], k = 2 untuk 6, arr = [2,3,4,7,11], k = 5 untuk 9, jujukan yang hilang dari 1, ekor berterusan, k=1, dan tatasusunan satu elemen. Periksa juga batas integer dalam bahasa yang dipilih.

Model jawapan berkualiti tinggi

Saya akan mentakrifkan bilangan integer positif yang hilang sehingga indeks i sebagai arr[i] - i - 1. Memandangkan tatasusunan meningkat secara tegas, kiraan itu adalah monotonik, jadi saya melakukan carian binari untuk indeks pertama yang kiraannya sekurang-kurangnya k. Jika sempadan ialah i, nilai hilang ke-k ialah k + i; menetapkan sempadan kanan kepada n secara semula jadi mengendalikan jawapan selepas nilai maksimum tatasusunan.

Saya menggunakan selang separuh terbuka [left, right). Apabila missing(mid) kurang daripada k, sempadan berada di sebelah kanan; jika tidak, saya kekalkan mid. Hasilnya ialah k + left, dalam masa O(log n) dan ruang O(1). Saya menguji jurang permulaan, jurang akhiran, tatasusunan berterusan, elemen tunggal, dan beberapa nilai k, serta membandingkan dengan oracle berasaskan imbasan.

Kesilapan lazim

• Menulis arr[i] - i dan tertinggal sebutan tolak satu.
• Mencari kedudukan false terakhir tetapi menggunakan formula jawapan true pertama.
• Menetapkan right kepada n - 1 dan salah mengendalikan jawapan selepas tatasusunan.
• Menggunakan formula apabila input tidak diisih atau mengandungi pendua.
• Menguji contoh sahaja dan terlepas pandang [1,2,3], [2], atau ekor berterusan.
• Mendakwa carian binari sentiasa lebih pantas tanpa membincangkan input yang diisih dan pemalar n kecil.

Pertukaran pelaksanaan

Pilih pengimbasan linear atau carian binari daripada saiz data dan kontrak sempadan, kemudian sahkan invarian dengan ujian.

Soalan susulan dan jawapan

Mengapakah kiraan yang hilang bersifat monotonik?

Peningkatan tegas bermakna nilai seterusnya bertambah sekurang-kurangnya satu. Apabila indeks bertambah sebanyak satu, nilai juga bertambah sekurang-kurangnya satu, jadi arr[i] - i - 1 tidak boleh berkurang.

Bagaimana jika tatasusunan tidak diisih atau mempunyai pendua?

Tukar kontrak terlebih dahulu: isih, hapuskan pendua, dan kekalkan nilai positif. Pengisihan menelan kos sekurang-kurangnya O(n log n); hanya selepas itu formula kiraan hilang asal terpakai. Jangan menuntut O(log n) untuk input yang tidak diisih.

Bilakah imbasan linear lebih diutamakan?

Untuk tatasusunan pendek, satu pertanyaan, atau strim tanpa capaian rawak, pengimbasan adalah lebih mudah. Carian binari mengandaikan input diisih dengan capaian rawak serta mempunyai kos persediaan dan pemalar.

Bagaimanakah anda mengembalikan k nilai hilang pertama?

Cari sempadan nilai, kemudian jana nilai dengan penunjuk tatasusunan dalam masa output O(k). Kerja output tidak boleh disembunyikan di dalam tuntutan O(log n).

Bagaimanakah anda mengelakkan limpahan (overflow) untuk k atau nilai yang besar?

Gunakan integer selamat atau jenis 64-bit dan periksa k + left serta arr[i] - i - 1. Jika kejituan sewenang-wenangnya dibenarkan, nyatakan BigInt atau perwakilan yang setara dalam antara muka dan ujian.

Rubrik pemarkahan

Calon yang kuat menerbitkan predikat monotonik, melaksanakan carian separuh terbuka, dan menerangkan formula jawapan. Calon yang hanya mengingati kod dan tidak dapat membuktikan sempadan memerlukan siasatan lanjut.