Meniň LeetCode 41-nji meseleme bolan höwesim: Birinji ýitirýän musbat san tapgyryna çuňňur göz aýlamak

LeetCode-niň “Birinji ýitap düşen musbet san” (41-nji noňr) meselesi meniň soňky koduň işine bolan höwesime öwrüldi. Bu, aldap bilýänlik ýüzünden ýönekeý taýdan görünýän, pikirlerimi eýeleýän we onuň çylşyrymlyklaryny gözlemäge, mümkin bolan iň netijeli TypeScript çözgüsini döretmäge iterýän tapgyr. Bu ýazgy diňe koduň interwýularyny üstünlikli geçmek bilen bagly däl (şonuň üçin ýakap ýetýän artykmaçlyk bolsa-da). Bu, mesele çözmegiň arassa şatlygy, optimizasiýanyň täsirliligi we netijeli koduň owadan gözelligi bilen bagly. Şeýle hem, men biraz matematika höwesdar bolanymy üçin, çözgüniň matematika esasyny hem içine alyp bileris.

Mesele: Goýnyň içindäki kurt

Mesele sanlaryň düzülmedik massivini görkezýär. Siziň wezipäňiz: iň kiçi ýitap düşen musbet san tapmak. Ýönekeý görünýärmi? Ýene-de pikir ediň. $O(n)$ wagt we $O(1)$ giňişlik çylşyrymlylygy bu ýönekeý görnüşli wezipäni kyn algoritmik tapgyra öwürýär.

Ilkinji kynçylyklar: Käte güýçli çözgüniň tuzagy

Ilkinji synanyşyklarım düzülemegi ( $O(n)$ wagt çylşyrymlylygyny bozýar) we heş toplumyny ( $O(1)$ giňişlik çäkden aşýar) öz içine aldy. Aýdyň, has kämil usul gerekdi.

“Ýehu!” pursady: Ýerinde üýtgetmeler

Esasy düşünje, giriş massiwini özünde heş tablisa hökmünde ulanyp boljakdygyny düşünmek boldy. Elementleri gaýtadan düzmek bilen, $x$ sanlaryny $x - 1$ indeksine goýup bileris (eger $1 \le x \le n$ bolsa, munuň n massiwiniň uzynlygy). Bu ýerinde üýtgetmeler netijeli çözgüniň ýoluny açýar.

Koduň ösüş taryhy: TypeScript dessany

Mysal üçin, düşündirişler we matematika düşünjeleri bilen koduň ösüş taryhyny görkezýärin:

1-nji nusga: Ýönekeý çemeleşme (ortaks çalşyklaryň bilen)

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

  // Eger [1, n] aralygynda bolsa, her bir san öz dogry pozisiýasyna goýulýar
  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]] // Çalşyk
    }
  }

  // Iň birinji ýitap düşen musbet san tapylýar
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // Eger ähli sanlar öz dogry pozisiýalarynda bolsa, ýitap düşen san n + 1
  return n + 1
}

Bu nusga, işjeň bolsa-da, ortaks çalşyklardan ejir çekýär. Iň ýaramaz ýagdaýda çalşyklaryň sany $O(n^2)$ golaýlaşýar, emma ortaça ýagdaý $O(n)$ golaýlaşýar.

Düşündiriş:

1. Massiwi gaýtadan düzmek: Her bir nums[i] san [1, n] aralygynda we heniz dogry pozisiýada däl bolsa, öz "dogry" indeksi (nums[i] - 1)-e goýulýar.

2. Ýitap düşen musbet san tapmak: Gaýtadan düzülenden soň, nums[i] !== i + 1 bolan ilkinji i indeksi i + 1-iň ýitap düşen musbet san bolandygyny görkezýär.

3. Gerek bolsa n + 1 gaýtarmak: Eger 1-den n-e çenli ähli sanlar dogry pozisiýalarda bolsa, ýitap düşen san n + 1 bolýar.

Esasy nokatlar:

• Ýerinde gaýtadan düzmek: Goşmaça giňişlik ulanmazlygy üçin massiwiň özüni üýtgedýäris.
• Netijeliligi: Hem gaýtadan düzmek, hem-de soňky gözlem $O(n)$ wagt alýar, optimal işlemegi üpjün edýär.

2-nji nusga: Netijeliligi ýokarlandyrmak (ortaks çalşyklary aradan aýyrmak)

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

  // Mümkin bolsa, sanlary öz dogry pozisiýalaryna gaýtadan düzmek
  while (idx < n) {
      const correctIdx = nums[idx] - 1
      if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
          // Goşmaça ulanmazdan çalşyk etmek
          ;[nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]
      } else {
          idx++
      }
  }

  // Iň birinji ýitap düşen musbet san tapmak
  for (let i = 0; i < n; i++) {
      if (nums[i] !== i + 1) {
          return i + 1
      }
  }

  return n + 1
}

Düşündiriş:

1. Netijeli gaýtadan düzmek:

   • while döwri elementleri dogry pozisiýalaryna (nums[idx] - 1) diňe san [1, n] aralygynda we heniz dogry pozisiýada däl bolsa, çalşyk edýär.
   • if şerti geçmez ýa-da dogry bolan sanlary zerur bolmadyk çalşyklardan gaça saklaýar.

2. Dogry indeksi barlamak:

   • Gaýtadan düzmek tapgyrynda, geçmez çalşyklar we ortaks amallar nums[idx]-iň aralygyny we gymmatyny barlamak bilen önüňden çykarylýar.

3. Ýadyň netijeli çalşygy:

   • Destrukturlaşdyrmagyň ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) ulanylmagy goşmaça ulanmaga gerek bolmazlygyny, ýadyň ulanylmagyny azaldýar.

4. Az döwür:

   • Algoritma diňe iki sany lineýer geçişi ulanýar:
     • Massiwi ýerinde gaýtadan düzmek üçin biri.
     • Iň birinji ýitap düşen musbet san tapmak üçin beýlekisi.

Çylşyrymlylyk analizi:

• Wagt çylşyrymlylygy:
  • while döwri we for döwri hem $O(n)$ işlär, umumy wagt çylşyrymlylygyny $O(n)$ edýär.
• Giňişlik çylşyrymlylygy:
  • Algoritma goşmaça maglumat gurluşlaryny ulanmazdan ýerinde işlär, şonuň üçin giňişlik çylşyrymlylygy $O(1)$ bolýar.

Näme üçin bu kod optimal:

• Netijeliligi: Özleşdirilen while döwri ortaks amallary azaldýar, tizligi ýokarlandyrýar.
• Ýadyň netijeliligi: Ýerinde çalşygyň we goşmaça ulanmagyň ulanylmazlygy iň pes ýadyň ulanylmagyny üpjün edýär.

3-nji nusga: Ýady üçin optimizasiýa edilen (iň az ýadyň ulanylmagy)

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
}

Ýadyň esasy optimizasiýalary:

1. Iň az wagtlaýyn ulanmagyň ýerinde täzelenmeleri:

   • Çalşyk üçin temp ulanmakdan gaça, bu kod massiwi nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1 bilen gönüden-göni üýtgedýär.
   • Bu goşmaça ulanmaga gerek bolmazlygyny, ýadyň ulanylmagyny saklaýar.

2. Döwrde az wagtlaýyn gymmatlyklar:

   • Kod correctIdx-i döwrde gönüden-göni hasaplaýar, esasy logikadan daşarda goşmaça arakesme ulanmaga gerek bolmazlygyny saklaýar.
   • Az ulanmagyň bellenmegi her iterasiýada ýadyň ulanylmagyny azaldýar.

3. Gaýtadan düzmek üçin ýekeje geçiş:

   • while döwründe iç içe şertleri ulanýan ilkinji koddan tapawutlylykda, bu ýerine ýetiriliş çalşyklary tamamlaýar ýa-da indeksi has ýönekeý usul bilen öňe sürýär, iş wagtynyň giňişligini we ýadyň ulanylmagyny azaldýar.
   • Döwr gurluşy (while ýekeje ýokarlanma ýa-da gaýtadan düzme bilen) has gönüden-göni bolup, az goşmaça gymmatlyklary talap edýär.

4. Ortaks barlamalar ýok:

   • correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] üçin barlamalar gysga we netijä goşant goşmazlyk üçin ortaks amallaryň öňüni alýar.
   • Bu goşmaça serişdeleri zerur bolmadyk amallar üçin bölüp bermegiň zerurlygyny aradan aýyrýar.

Näme üçin bu ýady üçin tapawut edýär:

• Az wagtlaýyn saklama: temp ulanmazdan we arakesme hasaplamalaryny azaltmak bilen, ýadyň ulanylmagy kiçiräýär.
• Özleşdirilen ýerine ýetiriliş: Az ädimler we ýönekeý logika her amalda ýadyň ulanylmagyny azaldýar.
• Kesh ulanylmagynyň ýokarlanmagy: Algoritmiň lineýar, çak edilýän giriş modeli CPU keshiň işini ýokarlandyrýar, bilýär ýaly ýadyň ulanylmagyny azaldýar.

Bu çözgüniň gönüden-göni ýerinde täzelenmelere, az ulanmaga we netijeli ýadyň giriş modelline üns bermegi onuň ýadyň netijeliligi babatynda iň gowydygyny görkezýär. Saklama konstant ($O(1)$) bolup bilsä-de, LeetCode ýaly bäsleşikli platformalarda, esasanam uly maglumatlar üçin hasaplamaga ýeterlik derejede uly.

4-nji nusga: Optimizasiýa edilen şaýmerdan (Ýerinde çalşyk, wagtlaýyn ýok)

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
}

Bu soňky nusga hem optimal işlemegi, hem-de az ýadyň ulanylmagyny wagtlaýyn ulanmazdan özleşdirilen ýerinde çalşyk bilen gazanýar. Wagt çylşyrymlylygy indi berk $O(n)$, giňişlik çylşyrymlylygy $O(1)$ bolup, ähli talaplary ýerine ýetirýär. Matematika taýdan, elementleri öz “dogry” pozisiýalaryna goýmak üçin massiwiniň içinde bir görnüşli permutasiýa geçirýäris.

nums[i] === nums[nums[i] - 1] barlamasyny goşmak bilen, zerur bolmadyk çalşyklaryň öňüni alýarys. Bu netijeliligi ep-esli derejede ýokarlandyrýar, wagt çylşyrymlylygyny islenilen $O(n)$ golaýlaşdyrýar.

Ýerine ýetirilişdäki esasy tapawutlar:

1. Ortaks çalşyklaryň öňüni almak:

   • Berilen kod çalşygy ýerine ýetirmezden ozal nums[i] === nums[nums[i] - 1]-i anyk barlaýar. Bu san dogry pozisiýada ýa-da takrarlananlar bar bolsa, zerur bolmadyk çalşyklaryň öňüni alýar.
   • Ilkinji ýerine ýetirilişde bu barlama goýberilýär, zerur bolmadyk çalşyklara, esasanam uly massivler üçin goşmaça iş ýükini döredýär. Her goşmaça çalşyk, esasanam uly massivler üçin goşmaça iş ýükini döredýär.

2. Dogry indeksi deňeşdirmek:

   • Berilen kod san dogry ýerleşdirilen ýa-da geçmez şert ýerine ýetirilençä, öz dogry pozisiýasyna gaýta-gaýta çalşyk edilmegine kepil etmek üçin while (nums[i] !== i + 1) ulanýar. Bu zerur bolmadyk döwür iterasiýalaryny aradan aýyrýar.
   • Ilkinji kod döwür şerti içinde sany niýetlenilen indeksi bilen deňeşdirmeýär. Sanlaryň az herekete gerek bolan ýagdaýlarynda has köp amaly ýerine ýetirip biler.

3. Optimizasiýa edilen şertli barlamalar:

   • Şertleri ýekeje if blokunda birleşdirmek bilen (mysal üçin, nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]), kod zerur bolmadyk barlamalardan ýa-da hasaplamalardan goşmaça iş ýükiniň öňüni alýar.

Näme üçin bu LeetCode-da wajyp:

• Iş wagtynyň durnuklylygy:

  • LeetCode-niň iş wagtynyň ölçegleri zerur bolmadyk amallara, mysal üçin ortaks çalşyklara ýa-da goşmaça deňeşdirmelere duýgur bolup biler.
  • Berilen kod bu amallary azaldýar, ortaça has tiz iş wagtyny berýär.

• Kesh netijeliligi:

  • Az çalşyklar we ýönekeý döwür logikasy CPU keshiň ulanylmagyny ýokarlandyrýar. Häzirki zaman prosessorlar çak edilýän we özleşdirilen giriş modellärinden peýdalanýarlar, bu berilen kod görkezýär.

Netijeler

Mysal üçin, umumylykda görkezilen tablisanyň görnüşinde:

Bu tablisa deňagramlyklary we soňky çözgüniň optimallığını görkezýär.

Umumylykda, iň gowy işlemegi we ýady üçin synanyşygyň hakykatdan-da iň optimizasiýa edilendigini görkezýär:

• 1 ms iş wagty: Işlemegiň babatynda iň tiz netijä laýyk gelýär.
• 58.9 MB ýadyň ulanylmagy: "Iň gowy ýady" nusgasyna garaňda birneme ýokary, ýöne beýleki synanyşyklara garaňda pes.

Analiz:

1. Iş wagty:

   • 1 ms iş wagty optimizasiýa edilen çemeleşigiň ortaks barlamalary we zerur bolmadyk çalşyklary aradan aýyrýandygyny görkezýär.
   • $O(n)$-iň durnukly wagt çylşyrymlylygy uly maglumatlar üçin ölçeglenilmegine kepil edýär.

2. Ýady:

   • 58.9 MB bäsleşikli bolup, tiz ýerine ýetirilişe garamazdan ýadyň ulanylmagynyň pesdigini görkezýär. "Iň gowy ýady" (58.5 MB) bilen bu kiçi ulylyk tapawudy destrukturlaşdyrma ýa-da maşynyň özleşdirilen işlemeginde tapawudyň netijesi bolup biler.

3. Deňagramlyklar:

   • "Iň gowy ýady" çözgüsi pes ýadyň ulanylmagy üçin iş wagtyny biraz gurban berýär.
   • "Iň gowy işlemegi" çözgüsi tizlige has köp üns berýär, ýöne az-kem has köp ýady ulanýar.

Netije:

Optimizasiýa edilen çözgüt gowy deňagramlygy döredýär:

• 1 ms iş wagty iň gowy işlän kod bilen deň.
• 58.9 MB ýadyň ulanylmagy iň gowy ýady netijesine golaý, az goşmaça ýük bilen.

Bu, esasanam işlemegi we ýady hem möhüm bolan ýagdaýlar üçin gowy saýlanyş bolup durýar.

Matematika esasy: Döwür permutasiýalary we guşhana ýörelgesi

Esasy pikir döwür permutasiýalarynyň düşünjesiniň daşyndan çykýar. Her bir $x$ sanyny $x - 1$ indeksine goýmak maksady bilen döwür döretmäge çalyşýarys. while döwri bu döwürleri netijeli geçýär, her bir elementi öz bellenen ýerini tapmagyny üpjün edýär.

Guşhana ýörelgesi bu ýerde ýumşak rol oýnaýar. $n$ sany mümkin pozisiýa (0-den $n-1$-e çenli indeksler) bar we $[1, n+1]$ aralygynda ýitap düşen musbet san tapýarys, eger 1-den n-e çenli ähli sanlar bar bolsa, ýitap düşen san $n + 1$ bolmaly.

Höwes dowam edýär...

LeetCode 41-e bolan höwesim galýar. Men yzygiderli has köp optimizasiýa we çuň düşünjeleri gözleýärin. Bu gözlegde maňa goşuluň! Pikirleriňizi, öz çözgüleriňizi paýlaşyň we matematikaniň we algoritmleriň owadan kesişişini bilelikde gözleýeliň.