Obsesioni im me LeetCode 41: Një zhytje e thellë në enigmën e numrit të parë pozitiv që mungon

Problemi "Numri i Parë Pozitiv që Mungon" në LeetCode: Një Odise Koduese

Problemi "Numri i Parë Pozitiv që Mungon" (numri 41) në LeetCode është bërë obsesioni im i fundit në kodim. Është një enigmë e thjeshtë në pamje të parë, por që më ka zënë mendjen, duke më shtyrë të eksploroja hollësitë e saj dhe të krijoj zgjidhjen më efikase të mundshme në TypeScript. Ky postim nuk ka të bëjë vetëm me suksesin në intervistat e kodimit (edhe pse kjo është një përfitim i mirë). Ka të bëjë me gëzimin e pastër të zgjidhjes së problemeve, emocionin e optimizimit dhe bukurinë elegante të kodit efikas. Dhe, sepse jam paksa maniak i matematikës, do të zhytemi edhe në bazat matematikore të zgjidhjes.

Problemi: Një Ujk i Maskuar si Dele

Problemi paraqet një varg të pasortuar të numrave të plotë. Detyra juaj: gjeni numrin e parë pozitiv që mungon. Duket e thjeshtë? Mendoni përsëri. Kufizimet e kohës $O(n)$ dhe hapësirës $O(1)$ e shndërrojnë këtë detyrë në dukje të thjeshtë në një enigmë algoritmike sfiduese.

Vështirësitë Fillestare: Kurthi i Forcës Brute

Të përpjekjet e mia fillestare përfshinin sortim (duke shkelur kufizimin e kohës $O(n)$) dhe grupe hash (duke tejkaluar kufirin e hapësirës $O(1)$). Qartë, nevojitej një qasje më e sofistikuar.

Momenti "Eureka": Transformimi në Vend

Ideja kryesore ishte të kuptoja se mund të përdor vetë vargun e hyrjes si një tabelë hash. Duke rregulluar elementët, mund të vendos numrin $x$ në indeksin $x - 1$ (nëse $1 \le x \le n$, ku $n$ është gjatësia e vargut). Ky transformim në vend çel rrugën drejt një zgjidhjeje efikase.

Evolucioni i Kodit: Një Sagë TypeScript

Ja kronika e evolucionit të kodit tim, me shpjegime të detajuara dhe intuita matematikore:

Versioni 1: Qasja Naive (me Shkëmbime të Tepërta)

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

  // Vendosni secilin numër në pozicionin e tij të saktë nëse është në rangun [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]] // Shkëmbim
    }
  }

  // Gjeni numrin e parë pozitiv që mungon
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // Nëse të gjithë numrat janë në pozicionet e tyre të sakta, numri që mungon është n + 1
  return n + 1
}

Ky version, ndonëse funksional, vuan nga shkëmbime të tepërta. Numri i shkëmbimeve në skenarin më të keq afrohet me $O(n^2)$, megjithëse rasti mesatar është më afër $O(n)$.

Shpjegimi:

1. Rregullimi i vargut: Secili numër nums[i] vendoset në indeksin e tij "të saktë" (nums[i] - 1) nëse është brenda rangut [1, n] dhe nuk është tashmë në pozicionin e saktë.

2. Identifikimi i numrit pozitiv që mungon: Pas rregullimit, indeksi i parë i ku nums[i] !== i + 1 tregon se i + 1 është numri i plotë pozitiv që mungon.

3. Kthimi i n + 1 nëse nevojitet: Nëse të gjithë numrat nga 1 deri në n janë në pozicionet e tyre të sakta, numri që mungon është n + 1.

Pikë Kyçe:

• Rregullim në vend: Modifikojmë vetë vargun për të shmangur përdorimin e hapësirës shtesë.
• Efikasitet: Si rregullimi ashtu edhe skanimi përfundimtar marrin kohë $O(n)$, duke siguruar performancë optimale.

Versioni 2: Rritje e Performancës (Eliminimi i Shkëmbimeve të Tepërta)

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

  // Rregullimi i numrave në pozicionet e tyre të sakta nëse është e mundur
  while (idx < n) {
    const correctIdx = nums[idx] - 1
    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      // Shkëmbim pa përdorur një variabël të përkohshme
      ;[nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]
    } else {
      idx++
    }
  }

  // Identifikimi i numrit të parë pozitiv që mungon
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

Shpjegimi:

1. Rregullim Efikas:

   • Bucle while shkëmben elementet direkt në pozicionet e tyre të sakta (nums[idx] - 1) vetëm kur numri është në rangun e vlefshëm [1, n] dhe nuk është tashmë në pozicionin e tij të saktë.
   • Kushti if siguron që numrat e pavlefshëm ose tashmë të saktë të kalohen pa shkëmbime të panevojshme.

2. Kontrollim i Drejtpërdrejtë i Indeksit:

   • Gjatë fazës së rregullimit, shkëmbimet e pavlefshme dhe operacionet e tepërta shmangen duke kontrolluar rangun dhe vlerën e nums[idx].

3. Shkëmbim i Efikasëm i Memorisë:

   • Përdorimi i dekonstruksionit ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) eliminon nevojën për një variabël të përkohshme, duke minimizuar përdorimin e memories.

4. Bucle Mininale:

   • Algoritmi përdor vetëm dy kalime lineare:
     • Një për të rregulluar vargun në vend.
     • Një tjetër për të gjetur numrin e parë pozitiv që mungon.

Analiza e Kompleksitetit:

• Kompleksiteti i Kohës:
  • Bucle while dhe bucle for të dyja funksionojnë në $O(n)$, duke bërë që kompleksiteti total i kohës të jetë $O(n)$.
• Kompleksiteti i Hapësirës:
  • Algoritmi vepron në vend pa përdorur struktura të dhënash ndihmëse, kështu që kompleksiteti i hapësirës është $O(1)$.

Pse Ky Kod është Optimal:

• Performanca: Bucle while e rrjedhshme siguron operacione minimale të tepërta, duke maksimizuar shpejtësinë.
• Efikasiteti i Memorisë: Përdorimi i shkëmbimit në vend dhe shmangia e variablave shtesë siguron gjurmën më të ulët të mundshme të memories.

Versioni 3: I Optimizuar për Memorie (Përdorim Minimal i Hapësirës)

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
}

Optimizimet Kyçe të Memorisë:

1. Përditësime në Vend me Variabla të Përkohshme Minimale:

   • Në vend të përdorimit të një variabli temp për shkëmbim, ky kod modifikon direkt vargun me nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1.
   • Kjo eliminon nevojën për një variabël të përkohshme, duke ulur ngarkesën e memories me një sasi konstante.

2. Vlera më pak të Përkohshme në Bucle:

   • Kodi llogarit correctIdx direkt në bucle, duke shmangur nevojën për të ruajtur variabla të ndërmjetëm shtesë jashtë logjikës kryesore.
   • Caktimet më pak të variablave do të thotë përdorim pak më i ulët i memories për secilën iteracion.

3. Kalim i Vetëm për Rregullim:

   • Ndryshe nga kodi i parë që përdor kushte të ngulitura në bucle while, ky implementim përfundon shkëmbimet ose e avancon indeksin në një mënyrë më të rrjedhshme, duke ulur thellësinë e grumbullit të kohës së ekzekutimit dhe përdorimin e memories.
   • Struktura e bucles (while me një rritje ose rregullim të vetëm) është më e drejtpërdrejtë, duke kërkuar më pak vlera ndihmëse.

4. Kontrollime pa Tepri:

   • Kontrollat për correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] janë të përmbledhur dhe parandalojnë operacione të panevojshme që mund të përdorin përkohësisht memorien e grumbullit ose të cache-it të procesorit.
   • Kjo shmang nevojën për të ndarë burime shtesë për operacione që nuk do të kontribuojnë në rezultat.

Pse Kjo Bën Dallim në Memorie:

• Ruajtje e Ulët e Përkohshme: Duke mos mbështetur në një variabël temp dhe duke minimizuar llogaritjet e ndërmjetme, gjurma e memories është më e vogël.
• Ekzekutim i Arrjedhshëm: Hapat më pak dhe logjika më e thjeshtë përkthehen në përdorim më të ulët të memories për secilin operacion.
• Përdorim i Përmirësuar i Cache-it: Modeli i aksesit linear dhe i parashikueshëm i algoritmit përmirëson performancën e cache-it të procesorit, duke ulur indirekt ngarkesën e memories.

Ky fokus i zgjidhjes në përditësimet direkte në vend, përdorimin minimal të variablave dhe modelet efikase të aksesit të memories e bën atë më të mirën në aspektin e efikasitetit të memories. Ndërsa kursimet janë konstante ($O(1)$), ato janë mjaft të rëndësishme për t'u regjistruar në platforma konkurruese si LeetCode, veçanërisht për grupe të mëdha të të dhënave.

Versioni 4: Kryevepra e Optimizuar (Shkëmbim në Vend, Pa 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
}

Ky version përfundimtar arrin si performancë optimale ashtu edhe përdorim minimal të memories përmes shkëmbimit elegant në vend pa një variabël të përkohshme. Kompleksiteti i kohës është tani fuqishëm $O(n)$, dhe kompleksiteti i hapësirës është $O(1)$, duke përmbushur të gjitha kërkesat. Matematikisht, ne po kryejmë një lloj permutacioni ciklik brenda vargut për të vendosur elementët në pozicionet e tyre "të sakta".

Duke shtuar një kontroll (nums[i] === nums[nums[i] - 1]), ne parandalojmë shkëmbime të panevojshme. Kjo përmirëson ndjeshëm performancën, duke e sjellë kompleksitetin e kohës më afër $O(n)$ të dëshiruar.

Dallimet Kyçe në Implementimin:

1. Shmangia e Shkëmbimeve të Tepërta:

   • Kodi i dhënë kontrollon në mënyrë eksplicite nëse nums[i] === nums[nums[i] - 1] para se të kryejë shkëmbimin. Kjo shmang shkëmbime të panevojshme kur numri është tashmë në pozicionin e saktë ose ekzistojnë kopje.
   • Në implementimin e parë, ky kontroll është i lënë jashtë, duke çuar potencialisht në shkëmbime të tepërta edhe kur janë të panevojshme. Secili shkëmbim shtesë shton ngarkesë, veçanërisht për vargje më të mëdha.

2. Krahasim i Drejtpërdrejtë i Indeksit:

   • Kodi i dhënë përdor while (nums[i] !== i + 1) për të siguruar që një numër të shkëmbehet vazhdimisht në pozicionin e tij të saktë derisa të vendoset siç duhet ose të plotësohet një kusht i pavlefshëm. Kjo eliminon iteracione të panevojshme të bucles.
   • Kodi i parë nuk krahasohet në mënyrë eksplicite numrin me indeksin e tij të synuar brenda kushtin e bucles. Mund të kryejë më shumë operacione në raste ku numrat kanë nevojë për lëvizje minimale.

3. Kontrollet e Optimizuara të Kushteve:

   • Duke kombinuar kushtet në një bllok if të vetëm (p.sh., nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]), kodi shmang ngarkesën shtesë nga kontrollat ose llogaritjet e panevojshme.

Pse Kjo Ka Rëndësi në LeetCode:

• Konsistenca e Kohës së Ekzekutimit:

  • Matjet e kohës së ekzekutimit të LeetCode mund të jenë të ndjeshme ndaj operacioneve të panevojshme, të tilla si shkëmbime të tepërta ose krahasime shtesë.
  • Kodi i dhënë i minimizon këto operacione, duke çuar në kohë ekzekutimi më të shpejtë mesatarisht.

• Efikasiteti i Cache-it:

  • Shkëmbimet më pak dhe logjika më e thjeshtë e bucles rezultojnë në përdorim më të mirë të cache-it të procesorit. Procesori modern përfitojnë nga modelet e aksesit të parashikueshme dhe të rrjedhshme, të cilat kodi i dhënë i shfaq.

Rezultatet

Ja përmbledhja e paraqitur në një tabelë:

Kjo tabelë thekson kompromet e bëra dhe optimalitetin e zgjidhjes përfundimtare.

Përmbledhja tregon se përpjekja për performancën dhe memorien më të mirë është vërtet më e optimizuar, duke arritur:

• 1 ms kohë ekzekutimi: Duke iu përshtatur rezultatit më të shpejtë në aspektin e performancës.
• 58.9 MB përdorim i memories: Pak më i lartë se klloni "memoria më e mirë" por më i ulët se përpjekjet e tjera.

Analiza:

1. Koha e Ekzekutimit:

   • 1 ms koha e ekzekutimit tregon se qasja e optimizuar eliminon kontrollat e tepërta dhe shkëmbimet e panevojshme.
   • Kompleksiteti i kohës i qëndrueshëm i $O(n)$ siguron shkallëzimin për grupe të mëdha të të dhënave.

2. Memoria:

   • 58.9 MB është konkurruese, duke treguar se gjurma e memories është e ulët pavarësisht ekzekutimit të shpejtë. Ky rritje e vogël në krahasim me "memorien më të mirë" (58.5 MB) mund të jetë për shkak të ndryshimeve në dekonstruksion ose optimizime specifike të motorit.

3. Kompromet:

   • Zgjidhja "memoria më e mirë" sakrifikon pak kohën e ekzekutimit për përdorim më të ulët të memories.
   • Zgjidhja "performanca më e mirë" fokusohet më shumë në shpejtësi por përdor pak më shumë memorie.

Përfundimi:

Zgjidhja e optimizuar arrin një ekuilibër të mirë:

• 1 ms koha e ekzekutimit është aq e shpejtë sa kodi më i shpejtë.
• 58.9 MB përdorimi i memories është afër rezultatit të "memorisë më të mirë", me ngarkesë të papërfillshme.

Është një zgjidhje e rrumbullakët, veçanërisht për skenarë ku janë kritike si performanca ashtu edhe memoria.

Bazat Matematikore: Permutacione Ciklike dhe Parimi i Pigeonhole

Ideja kryesore rrotullohet rreth konceptit të permutacioneve ciklike. Qëllimi ynë është të krijojmë një cikël ku secili numër $x$ vendoset në indeksin $x - 1$. Bucle while kalon në mënyrë efektive këta cikle, duke siguruar që secili element të gjejë vendin e tij të caktuar.

Parimi i Pigeonhole luan një rol të hollë këtu. Meqenëse kemi $n$ pozicione të mundshme (indekse $0$ deri në $n-1$) dhe po kërkojmë një numër të plotë pozitiv që mungon brenda rangut $[1, n+1]$, nëse të gjithë numrat nga 1 deri në $n$ janë të pranishëm, numri që mungon duhet të jetë $n + 1$.

Obsesioni Vazhdon...

Magjia ime me LeetCode 41 mbetet. Unë jam vazhdimisht në kërkim të optimizimeve të mëtejshme dhe intuitave më të thella. Bashkohuni me mua në këtë kërkim! Ndani mendimet tuaja, zgjidhjet tuaja dhe le të eksplorojmë bashkë kryqëzimin elegant të matematikës dhe algoritmeve.