Kegilaan LeetCode 41 Saya: Penerokaan Mendalam tentang Teka-teki Positif Hilang Pertama

Masalah "First Missing Positive" (nombor 41) daripada LeetCode telah menjadi kegilaan pengaturcaraan saya yang terbaru. Ia adalah teka-teki yang kelihatan mudah tetapi sebenarnya mencabar, yang telah mencengkam pemikiran saya, mendorong saya untuk meneroka selok-beloknya dan menghasilkan penyelesaian TypeScript yang paling cekap. Tulisan ini bukan sekadar mengenai menguasai temu duga pengaturcaraan (walaupun itu adalah kelebihan yang bagus). Ia adalah mengenai kegembiraan semata-mata menyelesaikan masalah, keseronokan pengoptimuman, dan keindahan elegan kod yang cekap. Dan kerana saya sedikit 'nerd' matematik, kita juga akan menyelami asas matematik penyelesaiannya.

Masalahnya: Serigala Berpakaian Kulit Domba

Masalah ini membentangkan satu tatasusunan integer yang tidak tersusun. Tugas anda: cari integer positif terkecil yang hilang. Nampak mudah? Fikirkan semula. Kekangan masa $O(n)$ dan kerumitan ruang $O(1)$ mengubah tugas yang kelihatan mudah ini menjadi teka-teki algoritma yang mencabar.

Perjuangan Awal: Perangkap Kekasaran

Percubaan awal saya melibatkan pengisisan (melanggar kekangan masa $O(n)$) dan set hash (melebihi had ruang $O(1)$). Jelas sekali, pendekatan yang lebih canggih diperlukan.

Momen Eureka: Transformasi Dalam-Tempat

Pemahaman utama adalah menyedari bahawa saya boleh menggunakan tatasusunan input itu sendiri sebagai jadual hash. Dengan menyusun semula elemen, saya boleh meletakkan nombor $x$ pada indeks $x - 1$ (jika $1 \le x \le n$, di mana $n$ ialah panjang tatasusunan). Transformasi dalam-tempat ini membuka jalan kepada penyelesaian yang cekap.

Evolusi Kod: Saga TypeScript

Berikut adalah kronik evolusi kod saya, dengan penjelasan terperinci dan pandangan matematik:

Versi 1: Pendekatan Naif (dengan Pertukaran Berlebihan)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length

  // Letakkan setiap nombor pada kedudukan yang betul jika ia berada dalam julat [1, n]
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const correctIndex = nums[i] - 1
      ;[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]] // Tukar
    }
  }

  // Cari integer positif pertama yang hilang
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // Jika semua nombor berada pada kedudukan yang betul, nombor yang hilang ialah n + 1
  return n + 1
}

Versi ini, walaupun berfungsi, mengalami pertukaran berlebihan. Bilangan pertukaran dalam senario kes terburuk mendekati $O(n^2)$, walaupun purata kes lebih hampir kepada $O(n)$.

Penjelasan:

1. Susun semula tatasusunan: Setiap nombor nums[i] diletakkan pada indeks "betul" (nums[i] - 1) jika ia berada dalam julat [1, n] dan belum berada pada kedudukan yang betul.

2. Kenal pasti integer positif yang hilang: Selepas penyusunan semula, indeks pertama i di mana nums[i] !== i + 1 menunjukkan bahawa i + 1 ialah integer positif yang hilang.

3. Pulangkan n + 1 jika diperlukan: Jika semua nombor dari 1 hingga n berada pada kedudukan yang betul, nombor yang hilang ialah n + 1.

Titik Utama:

• Penyusunan semula dalam-tempat: Kita mengubah suai tatasusunan itu sendiri untuk mengelakkan penggunaan ruang tambahan.
• Kecekapan: Kedua-dua penyusunan semula dan imbasan akhir mengambil masa $O(n)$, memastikan prestasi yang optimum.

Versi 2: Peningkatan Prestasi (Menghapuskan Pertukaran Berlebihan)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  // Susun semula nombor kepada kedudukan yang betul jika boleh
  while (idx < n) {
    const correctIdx = nums[idx] - 1
    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      // Tukar tanpa menggunakan pembolehubah sementara
      ;[nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]
    } else {
      idx++
    }
  }

  // Kenal pasti integer positif pertama yang hilang
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

Penjelasan:

1. Penyusunan Semula yang Cekap:

   • Gelung while menukar elemen terus ke kedudukan yang betul (nums[idx] - 1) hanya apabila nombor itu berada dalam julat sah [1, n] dan belum berada pada kedudukan yang betul.
   • Keadaan if memastikan nombor yang tidak sah atau sudah betul diabaikan tanpa pertukaran yang tidak perlu.

2. Pemeriksaan Indeks Langsung:

   • Semasa fasa penyusunan semula, pertukaran yang tidak sah dan operasi berlebihan dielakkan dengan memeriksa julat dan nilai nums[idx].

3. Pertukaran yang Cekap Memori:

   • Penggunaan dekonstruksi ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) menghapuskan keperluan untuk pembolehubah sementara, meminimumkan penggunaan memori.

4. Gelung Minimum:

   • Algoritma hanya menggunakan dua lintasan linear:
     • Satu untuk menyusun semula tatasusunan dalam tempat.
     • Satu lagi untuk mencari integer positif pertama yang hilang.

Analisis Kerumitan:

• Kerumitan Masa:
  • Gelung while dan gelung for kedua-duanya berjalan dalam $O(n)$, menjadikan jumlah kerumitan masa $O(n)$.
• Kerumitan Ruang:
  • Algoritma beroperasi dalam tempat tanpa menggunakan sebarang struktur data tambahan, jadi kerumitan ruang ialah $O(1)$.

Mengapa Kod Ini Optimum:

• Prestasi: Gelung while yang diperkemas memastikan operasi berlebihan minimum, memaksimumkan kelajuan.
• Kecekapan Memori: Penggunaan pertukaran dalam-tempat dan pengelakan pembolehubah tambahan memastikan jejak memori serendah mungkin.

Versi 3: Dioptimumkan untuk Memori (Penggunaan Ruang Minimum)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  while (idx < n) {
    const correctIdx = nums[idx] - 1

    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      nums[idx] = nums[correctIdx]
      nums[correctIdx] = correctIdx + 1
    } else {
      idx++
    }
  }

  for (let idx = 0; idx < n; idx++) {
    if (nums[idx] !== idx + 1) {
      return idx + 1
    }
  }

  return nums.length + 1
}

Pengoptimuman Memori Utama:

1. Kemas Kini Dalam-Tempat dengan Pembolehubah Sementara Minimum:

   • Bukannya menggunakan pembolehubah temp untuk pertukaran, kod ini terus mengubah suai tatasusunan dengan nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1.
   • Ini menghapuskan keperluan untuk pembolehubah sementara, mengurangkan overhead memori dengan jumlah tetap.

2. Nilai Sementara yang Kurang dalam Gelung:

   • Kod ini mengira correctIdx terus dalam gelung, mengelakkan keperluan untuk menyimpan pembolehubah pertengahan tambahan di luar logik teras.
   • Penugasan pembolehubah yang lebih sedikit bermakna penggunaan memori sedikit lebih rendah bagi setiap lelaran.

3. Satu Lintasan untuk Penyusunan Semula:

   • Tidak seperti kod pertama yang menggunakan keadaan bersarang dalam gelung while, pelaksanaan ini melengkapkan pertukaran atau memajukan indeks dengan cara yang lebih diperkemas, mengurangkan kedalaman timbunan masa jalan dan penggunaan memori.
   • Struktur gelung (while dengan satu penambahan atau penyusunan semula) lebih langsung, memerlukan nilai tambahan yang lebih sedikit.

4. Tiada Semakan Berlebihan:

   • Semakan untuk correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] adalah ringkas dan mencegah operasi yang tidak perlu yang boleh sementara menggunakan memori timbunan atau cache CPU.
   • Ini mengelakkan keperluan untuk memperuntukkan sumber tambahan untuk operasi yang tidak akan menyumbang kepada keputusan.

Mengapa Ini Membuat Perbezaan dalam Memori:

• Penyimpanan Sementara yang Dikurangkan: Dengan tidak bergantung pada pembolehubah temp dan meminimumkan pengiraan pertengahan, jejak memori lebih kecil.
• Pelaksanaan yang Diperkemas: Langkah yang lebih sedikit dan logik yang lebih mudah diterjemahkan kepada penggunaan memori yang lebih sedikit bagi setiap operasi.
• Penggunaan Cache yang Diperbaiki: Corak akses linear dan boleh diramal algoritma meningkatkan prestasi cache CPU, secara tidak langsung mengurangkan overhead memori.

Fokus penyelesaian ini pada kemas kini dalam-tempat langsung, penggunaan pembolehubah minimum, dan corak akses memori yang cekap menjadikannya yang terbaik dari segi kecekapan memori. Walaupun penjimatan adalah tetap ($O(1)$), ia cukup signifikan untuk mendaftar pada platform kompetitif seperti LeetCode, terutamanya untuk set data yang besar.

Versi 4: Karya Agung yang Dioptimumkan (Pertukaran Dalam-Tempat, Tiada Temp)

function firstMissingPositive(nums: number[]): number {
  for (let i = 0; i < nums.length; i++) {
    while (nums[i] !== i + 1) {
      if (nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]) {
        break
      }

      const temp = nums[i]
      nums[i] = nums[temp - 1]
      nums[temp - 1] = temp
    }
  }

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return nums.length + 1
}

Versi akhir ini mencapai kedua-dua prestasi optimum dan penggunaan memori minimum melalui pertukaran dalam-tempat yang elegan tanpa pembolehubah sementara. Kerumitan masa kini kukuh $O(n)$, dan kerumitan ruang ialah $O(1)$, memenuhi semua keperluan. Secara matematik, kita melakukan sejenis permutasi kitaran dalam tatasusunan untuk meletakkan elemen pada kedudukan "betul" mereka.

Dengan menambah semakan (nums[i] === nums[nums[i] - 1]), kita mencegah pertukaran yang tidak perlu. Ini secara signifikan meningkatkan prestasi, menjadikan kerumitan masa lebih hampir kepada $O(n)$ yang dikehendaki.

Perbezaan Utama dalam Pelaksanaan:

1. Mengelakkan Pertukaran Berlebihan:

   • Kod yang diberikan secara jelas menyemak jika nums[i] === nums[nums[i] - 1] sebelum melakukan pertukaran. Ini mengelakkan pertukaran yang tidak perlu apabila nombor itu sudah berada pada kedudukan yang betul atau pendua wujud.
   • Dalam pelaksanaan pertama, semakan ini diabaikan, berpotensi membawa kepada pertukaran berlebihan walaupun tidak perlu. Setiap pertukaran tambahan menambah overhead, terutamanya untuk tatasusunan yang lebih besar.

2. Perbandingan Indeks Langsung:

   • Kod yang diberikan menggunakan while (nums[i] !== i + 1) untuk memastikan nombor itu berulang kali ditukar ke kedudukan yang betul sehingga ia diletakkan dengan betul atau keadaan tidak sah dipenuhi. Ini menghapuskan lelaran gelung yang tidak perlu.
   • Kod pertama tidak secara jelas membandingkan nombor itu dengan indeks yang dimaksudkan dalam keadaan gelung. Ia mungkin melakukan lebih banyak operasi dalam kes di mana nombor memerlukan pergerakan minimum.

3. Semakan Bersyarat yang Dioptimumkan:

   • Dengan menggabungkan syarat dalam satu blok if (cth., nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]), kod tersebut mengelakkan overhead tambahan daripada semakan atau pengiraan yang tidak perlu.

Mengapa Ini Penting dalam LeetCode:

• Konsistensi Masa Jalan:

  • Pengukuran masa jalan LeetCode boleh sensitif terhadap operasi yang tidak perlu, seperti pertukaran berlebihan atau perbandingan tambahan.
  • Kod yang diberikan meminimumkan operasi ini, yang membawa kepada masa jalan yang lebih pantas secara purata.

• Kecekapan Cache:

  • Pertukaran yang lebih sedikit dan logik gelung yang lebih mudah menghasilkan penggunaan cache CPU yang lebih baik. Pemproses moden mendapat manfaat daripada corak akses yang boleh diramal dan diperkemas, yang ditunjukkan oleh kod yang diberikan.

Keputusan

Berikut adalah ringkasan yang dibentangkan dalam format jadual:

Jadual ini menyerlahkan pertukaran dan keoptimuman penyelesaian akhir.

Ringkasan menunjukkan bahawa percubaan untuk prestasi dan memori terbaik memang paling optimum, mencapai:

• Masa jalan 1 ms: Menyamai keputusan terpantas dari segi prestasi.
• Penggunaan memori 58.9 MB: Sedikit lebih tinggi daripada klon "memori terbaik" tetapi lebih rendah daripada percubaan lain.

Analisis:

1. Masa Jalan:

   • Masa jalan 1 ms menunjukkan pendekatan yang dioptimumkan menghapuskan semakan berlebihan dan pertukaran yang tidak perlu.
   • Kerumitan masa yang konsisten $O(n)$ memastikan kebolehskalaan untuk set data yang lebih besar.

2. Memori:

   • 58.9 MB adalah kompetitif, menunjukkan bahawa jejak memori adalah rendah walaupun pelaksanaan pantas. Peningkatan sedikit ini berbanding "memori terbaik" (58.5 MB) mungkin disebabkan oleh perbezaan dalam dekonstruksi atau pengoptimuman khusus enjin.

3. Pertukaran:

   • Penyelesaian "memori terbaik" sedikit mengorbankan masa jalan untuk penggunaan memori yang lebih rendah.
   • Penyelesaian "prestasi terbaik" memberi tumpuan lebih kepada kelajuan tetapi menggunakan memori yang sedikit lebih banyak.

Kesimpulan:

Penyelesaian yang dioptimumkan mencapai keseimbangan yang baik:

• Masa jalan 1 ms sepantas kod yang berprestasi terbaik.
• Penggunaan memori 58.9 MB hampir dengan keputusan memori terbaik, dengan overhead yang boleh diabaikan.

Ia adalah pilihan yang menyeluruh, terutamanya untuk senario di mana kedua-dua prestasi dan memori adalah kritikal.

Asas Matematik: Permutasi Kitaran dan Prinsip Lubang Merpati

Idea teras berputar di sekitar konsep permutasi kitaran. Kita bertujuan untuk mencipta kitaran di mana setiap nombor $x$ diletakkan pada indeks $x - 1$. Gelung while berkesan melintasi kitaran ini, memastikan setiap elemen mencari tempat yang ditetapkan.

Prinsip Lubang Merpati secara halus memainkan peranan di sini. Oleh kerana kita mempunyai $n$ kedudukan yang mungkin (indeks $0$ hingga $n-1$) dan kita sedang mencari integer positif yang hilang dalam julat $[1, n+1]$, jika semua nombor dari 1 hingga $n$ hadir, nombor yang hilang mestilah $n + 1$.

Kegilaan Berterusan...

Keghairahan saya terhadap LeetCode 41 masih berterusan. Saya sentiasa mencari pengoptimuman lanjut dan pandangan yang lebih mendalam. Sertai saya dalam usaha ini! Kongsikan pemikiran anda, penyelesaian anda sendiri, dan mari kita meneroka persilangan elegan matematik dan algoritma bersama-sama.