Xidhiidhkayga LeetCode 41: Qoto dheer oo ku saabsan dhibaatada First Missing Positive

Waxaa igu cusub dhibaatada "First Missing Positive" ee LeetCode (lambarka 41), taas oo noqotay waxa ugu dambeeya ee aan ku mashquulsanahay barnaamijka. waa dhibaato u muuqata mid fudud laakiin aad u adag oo maskaxdayda qabsatay, taas oo igu dhiirigelisay inaan sahamiyo quruxdeeda iyo sidii aan ugu abuuri lahaa xal TypeScript oo aad u waxtar badan. Qoraalkan ma aha oo kaliya in la helo shaqo wanaagsan wareysiyada barnaamijka (inkasta oo ay tahay faa'iido fiican), laakiin waa ku saabsan farxada xallinta dhibaatooyinka, xiisaha hagaajinta, iyo quruxda koodhka waxtarka leh. Oo maxaa yeelay waxaan ahay qof jecel xisaabta, waxaan xataa ku dari doonaa aasaaska xisaabeed ee xalka.

Dhibaatada: Dhululubo ku dhex jirta Adhi

Dhibaatadu waxay soo bandhigaysaa shax aan la kala saarin oo ka kooban tirooyin dhan. Hawshaada: hel tirooyinka ugu yar ee la waayay. Miyaad u maleyneysaa mid toosan? Mar kale ka fikir. Xaddidaadyada wakhtiga $O(n)$ iyo booska $O(1)$ waxay dhibaatadan u beddelaan dhibaato farsamo oo adag.

Dhibka Hore: Qabka Xoogga Leh

Isku daygii ugu horreeyay waxaa ka mid ahaa kala saarid (oo jebiyay xaddidaadda wakhtiga $O(n)$) iyo hash sets (oo dhaafay xaddidaadda booska $O(1)$). Si cad, waxaa loo baahnaa hab aad u adag.

Xilligii Iftiinka: Isbedel Goobta

Fikradda ugu muhiimsan waxay ahayd in la ogaado inaan isticmaali karo shaxda gelitaanka laftiisa sida miis hash ah. Adigoo dib u habeynaya qaybaha, waxaan dhigi karaa lambarka $x$ booska $x - 1$ (haddii $1 \le x \le n$, halkaasoo $n$ ay tahay dhererka shaxda). Isbedelkan goobta ayaa furaha u ah xal waxtar leh.

Horumarka Koodhka: Sheekada TypeScript

Halkaan waxaa ku yaal taariikhda horumarka koodkayga, oo leh sharaxaad faahfaahsan iyo aragti xisaabeed:

Nooca 1: Habka Fudud (oo leh is-beddellada soo noqnoqda)

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

  // Meel dhig lambar kasta meeshiisa saxda ah haddii uu ku jiro inta u dhaxaysa [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]] // Is-beddel
    }
  }

  // Hel lambarka ugu yar ee la waayay
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // Haddii tirooyinka oo dhan ay yihiin meeshooda saxda ah, lambarka la waayay waa n + 1
  return n + 1
}

Noocan, inkastoo uu shaqeeyo, wuxuu la kulmaa is-beddellada soo noqnoqda. Tirada is-beddellada xaalada ugu xun waxay u dhowdahay $O(n^2)$, in kastoo kiiska celceliska uu u dhow yahay $O(n)$.

Sharaxaad:

1. Dib u habeynta shaxda: Lambarka kasta nums[i] waxaa lagu dhigayaa booska saxda ah (nums[i] - 1) haddii uu ku jiro inta u dhaxaysa [1, n] oo aan hore ugu jirin booska saxda ah.

2. Aqoonsashada lambarka togan ee la waayay: Ka dib dib u habeynta, booska ugu horreeya i halkaasoo nums[i] !== i + 1 ay tilmaamayso in i + 1 ay tahay lambarka togan ee la waayay.

3. Ku soo celi n + 1 haddii loo baahdo: Haddii tirooyinka oo dhan laga bilaabo 1 ilaa n ay ku jiraan meeshooda saxda ah, lambarka la waayay waa n + 1.

Qodobbada Muhiimka ah:

• Dib u habeynta goobta: Waxaan hagaajinaynaa shaxda lafteeda si aan uga fogaano isticmaalka boos dheeraad ah.
• Waxtarka: Labada dib u habeyn iyo baaritaanka ugu dambeeya waxay qaataan waqti $O(n)$, taas oo hubineysa waxqabadka ugu wanaagsan.

Nooca 2: Korodhka Waxqabadka (ka saarista is-beddellada soo noqnoqda)

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

  // Dib u habeynta tirooyinka meeshooda saxda ah haddii ay suurtogal tahay
  while (idx < n) {
    const correctIdx = nums[idx] - 1
    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      // Is-beddel aan isticmaalin isbeddel ku meel gaar ah
      ;[nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]
    } else {
      idx++
    }
  }

  // Aqoonsashada lambarka togan ee ugu horreeya ee la waayay
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

Sharaxaad:

1. Dib u habeyn waxtar leh:

   • Wareegga while wuxuu si toos ah ugu beddelaa qaybaha meeshooda saxda ah (nums[idx] - 1) oo keliya marka lambarka uu ku jiro inta u dhaxaysa [1, n] oo aan hore ugu jirin meeshiisa saxda ah.
   • Shuruudda if waxay hubisaa in tirooyinka aan sax ahayn ama horeba sax u ah la iska dayo iyada oo aan la samayn is-beddel aan loo baahnayn.

2. Hubinta Booska Tooska ah:

   • Xilliga dib u habeynta, is-beddellada aan sax ahayn iyo hawlgallada soo noqnoqda waa la iska ilaaliyaa iyadoo la hubinayo inta u dhaxaysa iyo qiimaha nums[idx].

3. Is-beddelka Keydinta Xasuusta:

   • Isticmaalka burburinta ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) waxay ka saartaa baahida isbeddel ku meel gaar ah, taas oo yareynaysa isticmaalka xasuusta.

4. Wareegyo yar:

   • Algorithm-ku wuxuu isticmaalaa laba wareeg oo toosan:
     • Mid si loo dib u habeeyo shaxda goobta.
     • Mid kale si loo helo lambarka togan ee ugu horreeya ee la waayay.

Falanqaynta adkaanta:

• Xaqiiqda wakhtiga:
  • Wareegga while iyo wareegga for labadoodaba waxay ku shaqeeyaan $O(n)$, taas oo ka dhigaysa adkaanta wakhtiga guud $O(n)$.
• Adkaanta booska:
  • Algorithm-ku wuxuu ku shaqeeyaa goobta iyada oo aan la isticmaalin wax qaab dhismeed xog ah oo dheeraad ah, sidaas darteed adkaanta booska waa $O(1)$.

Sababta Koodhkan uu yahay midka ugu fiican:

• Waxqabadka: Wareegga while ee la fududeeyay wuxuu hubiyaa hawlgallo soo noqnoqda oo yar, taas oo kordhinaysa xawaaraha.
• Waxtarka Xasuusta: Isticmaalka is-beddelka goobta iyo ka fogaanshaha isbeddellada dheeraadka ah waxay hubisaa raadka ugu yar ee suurtogalka ah ee xasuusta.

Nooca 3: Midka ugu fiican ee Xasuusta (Isticmaalka Xasuusta ugu yar)

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
}

Hagaajinta Muhiimka ah ee Xasuusta:

1. Cusboonaysiinta Goobta oo leh Isbeddellada Ku-meel-gaarka ah ee ugu yar:

   • Halkii laga isticmaali lahaa isbeddel temp ah oo lagu beddelo, koodhkan wuxuu si toos ah ugu hagaajinayaa shaxda leh nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1.
   • Tani waxay ka saartaa baahida isbeddel ku meel gaar ah, taas oo yareynaysa kharashka xasuusta oo dhan.

2. Qiimayaasha Ku-meel-gaarka ah ee yar ee Wareegga:

   • Koodhkan wuxuu si toos ah ugu xisaabiyaa correctIdx wareegga, ka fogaanshaha baahida loo qabo in la kaydiyo isbeddellada dheeraadka ah ee dibedda lojik-ga aasaasiga ah.
   • Tirada yar ee u qoondaynta isbeddellada waxay macnaheedu tahay isticmaalka xasuusta oo yar wareeg kasta.

3. Wareeg keliya oo lagu sameeyo dib u habeynta:

   • Ka duwan koodkii ugu horreeyay ee isticmaala shuruudo la dul saaray wareegga while, hirgelintaani waxay dhameystirtaa is-beddellada ama waxay horumarisaa booska si habsami leh, taas oo yareynaysa qoto dheerida stack-ga wakhtiga fulinta iyo isticmaalka xasuusta.
   • Qaab-dhismeedka wareegga (while oo leh koror ama dib u habeyn keliya) waa mid toosan, oo u baahan qiimayaal gargaar oo yar.

4. Hubin aan soo noqnoqon:

   • Hubinta correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] waa mid kooban oo ka hortagaysa hawlgallo aan loo baahnayn oo isticmaali kara xasuusta stack-ga ama CPU cache-ga.
   • Tani waxay ka hortagtaa baahida loo qabo in la qoondeeyo kheyraad dheeraad ah oo loogu talagalay hawlgallo aan ka qayb qaadan doonin natiijada.

Sababta Tani ay u Saamayso Xasuusta:

• Keydinta Ku-meel-gaarka ah oo yaraaday: Adigoon ku tiirsanayn isbeddel temp ah iyo yareynta xisaabinta dheeraadka ah, raadka xasuustu waa mid yar.
• Fulinta la fududeeyay: Tallaabooyin yar iyo lojik fudud waxay u tarjumaysaa isticmaalka xasuusta oo yar hawlgal kasta.
• Isticmaalka Cache-ga oo wanaagsan: Qaabka algorithm-ka ee toosan, oo la saadaalin karo waxay hagaajisaa waxqabadka CPU cache-ga, si dadbanna waxay yareysaa kharashka xasuusta.

Xalkaani wuxuu diiradda saarayaa cusboonaysiinta tooska ah ee goobta, isticmaalka isbeddellada yar, iyo qaababka gelitaanka xasuusta oo waxtar leh waxay ka dhigaysaa midka ugu fiican marka la eego waxtarka xasuusta. Inkastoo kaydinta ay tahay mid joogto ah ($O(1)$), haddana waa mid ku filan in lagu diiwaan geliyo barnaamijyada tartan sida LeetCode, gaar ahaan xogta balaaran.

Nooca 4: Masterpiece-ka La Hagaajiyay (Isbeddelka goobta, aan lahayn 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
}

Nooca ugu dambeeya wuxuu gaaraa labadaba waxqabadka ugu wanaagsan iyo isticmaalka xasuusta ugu yar iyada oo loo marayo is-beddelka goobta ee jilicsan oo aan lahayn isbeddel ku meel gaar ah. Adkaanta wakhtiga hadda waa $O(n)$, iyo adkaanta booska waa $O(1)$, taas oo buuxineysa dhammaan shuruudaha. Xisaab ahaan, waxaan samaynaynaa nooc ka mid ah isku-beddel wareegsan gudaha shaxda si loo dhigo qaybaha meeshooda "saxda ah".

Adigoo ku daraya hubin (nums[i] === nums[nums[i] - 1]), waxaan ka hortagnaa is-beddel aan loo baahnayn. Tani waxay si aad ah u hagaajineysaa waxqabadka, taas oo adkaanta wakhtiga u dhowaysa $O(n) ee la rabay.

Farqiga Muhiimka ah ee Hirgelinta:

1. Ka fogaanshaha is-beddellada soo noqnoqda:

   • Koodhkan la bixiyay wuxuu si cad u hubiyaa haddii nums[i] === nums[nums[i] - 1] ka hor inta uusan samayn isbeddelka. Tani waxay ka hortagtaa is-beddellada aan loo baahnayn marka lambarka horeba uu ku jiro booska saxda ah ama dhexgalka jira.
   • Hirgelintii ugu horreysay, hubintaan waa la iska daayaa, taas oo laga yaabo inay keento is-beddellada soo noqnoqda xitaa marka aan loo baahnayn. Isbeddel kasta oo dheeraad ah wuxuu ku darayaa kharash, gaar ahaan shaxahan waaweyn.

2. Isbarbardhigga Booska Tooska ah:

   • Koodhkan la bixiyay wuxuu isticmaalaa while (nums[i] !== i + 1) si loo hubiyo in lambar si joogto ah loogu beddelo meeshiisa saxda ah ilaa uu si sax ah loo dhigo ama xaalad aan sax ahayn la kulmo. Tani waxay tirtirtaa wareegyada aan loo baahnayn.
   • Koodkii ugu horreeyay ma barbar dhigo si cad lambarka booska loogu talagalay gudaha shuruuda wareegga. Waxay samayn kartaa hawlgallo badan xaaladaha ay tirooyinku u baahan yihiin dhaqdhaqaaq yar.

3. Hubinta shuruudaha ee la hagaajiyay:

   • Adigoo isku daraya shuruudaha hal block if ah (tusaale ahaan, nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]), koodhka wuxuu ka fogaadaa kharashka dheeraadka ah ee laga helo hubinta ama xisaabinta aan loo baahnayn.

Sababta Tani ay muhiim ugu tahay LeetCode:

• Isku-dheelitirnaanta wakhtiga fulinta:

  • Cabirka wakhtiga fulinta ee LeetCode wuxuu u nugul yahay hawlgallo aan loo baahnayn, sida isbeddellada soo noqnoqda ama barbar dhigyada dheeraadka ah.
  • Koodhkan la bixiyay wuxuu yareeyaa hawlgalladan, taas oo keenta wakhti fulin oo degdeg badan celcelis ahaan.

• Waxtarka Cache-ga:

  • Isbeddellada yar iyo lojik wareeg oo fudud waxay keenaan isticmaalka CPU cache oo wanaagsan. Processors-ka casriga ahi waxay ka faa'iideystaan qaababka gelitaanka oo la saadaalin karo oo la fududeeyay, taas oo koodhkan la bixiyay uu muujiyo.

Natiijooyinka

Halkaan waxaa ku yaal muuqaalka la soo bandhigay qaab miis ah:

Miisku wuxuu muujinayaa is-beddellada iyo heerka ugu wanaagsan ee xalka ugu dambeeya.

Muuqaalku wuxuu muujinayaa in isku dayga ugu fiican ee waxqabadka iyo xasuusta uu runtii yahay midka ugu waxtarka badan, kaas oo gaaraya:

• Wakhti fulin oo ah 1 ms: Isbarbardhigga natiijada ugu dhaqsaha badan marka la eego waxqabadka.
• Isticmaalka xasuusta oo ah 58.9 MB: Wax yar oo ka badan nooca "xasuusta ugu wanaagsan" laakiin ka hooseeya isku dayga kale.

Falanqayn:

1. Wakhtiga fulinta:

   • Wakhtiga fulinta ee 1 ms wuxuu muujinayaa habka la hagaajiyay wuxuu ka saaraa hubin aan loo baahnayn iyo is-beddel aan loo baahnayn.
   • Adkaanta wakhtiga ee joogtada ah ee $O(n)$ waxay hubisaa la qabsashada xogta waaweyn.

2. Xasuusta:

   • 58.9 MB waa mid tartan, taas oo muujinaysa in raadka xasuustu hooseeyo inkasta oo fulinta degdegga ah. Kordhinta yar ee ka badan "xasuusta ugu wanaagsan" (58.5 MB) waxay noqon kartaa sababtoo ah farqiga burburinta ama hagaajinta gaarka ah ee mishiinka.

3. Is-beddellada:

   • Xalka "xasuusta ugu wanaagsan" wax yar ayuu u dhimayaa wakhtiga fulinta si loo yareeyo isticmaalka xasuusta.
   • Xalka "waxqabadka ugu wanaagsan" wuxuu diiradda saarayaa xawaaraha laakiin wuxuu isticmaalaa xasuus yar oo dheeraad ah.

Gabagabo:

Xalka la hagaajiyay wuxuu leeyahay dheelitir wanaagsan:

• Wakhtiga fulinta ee 1 ms waa mid u dhakhso badan sida koodhka waxqabadka ugu fiican.
• Isticmaalka xasuusta oo ah 58.9 MB waa mid u dhow natiijada xasuusta ugu fiican, oo leh kharash yar oo yar.

Waa doorasho dhammaystiran, gaar ahaan xaaladaha ay labada waxqabad iyo xasuus muhiim yihiin.

Aasaaska Xisaabeed: Isku-beddellada Wareega iyo mabda'a Pigeonhole

Fikradda aasaasiga ah waxay ku wareegtaa fikradda isku-beddellada wareega. Waxaan ujeedno inaan abuurno wareeg halkaasoo lambar kasta $x$ lagu dhigo booska $x - 1$. Wareegga while wuxuu si wax ku ool ah ugu socdaalayaa wareegyadan, taas oo hubineysa in qayb kasta ay hesho meesheedii loogu talagalay.

Mebda'a Pigeonhole wuxuu si qarsoodi ah u door bidayaa halkan. Maadaama aan haysanno $n$ boos oo suurtogal ah (booska $0$ ilaa $n-1$) oo aan raadineyno lambar togan oo la waayay gudaha inta u dhaxaysa $[1, n+1]$, haddii dhammaan tirooyinka laga bilaabo 1 ilaa $n$ ay jiraan, lambarka la waayay waa inuu noqdaa $n + 1$.

Waxa aan ku sii socdaa...

Waxaan sii wadaa xiiseynta LeetCode 41. Waan si joogto ah u raadineynaa hagaajinta dheeraadka ah iyo aragtiyo qoto dheer. Ku biir safarkan! La wadaag fikradahaaga, xalalkaaga, oo aan si wadajir ah u sahaminno isgoysyada quruxda badan ee xisaabta iyo algorithm-yada.