Гирифтории ман ба LeetCode 41: Шинохти амиқ ба муаммои “Рақами мусбати гумшудаи аввал”

Мушкилоти "Рақами мусбати гумшуда"-и LeetCode (рақами 41) ба машғулияти охирини кодингии ман табдил ёфт. Ин як муаммои фиребкорона сода аст, ки фикрҳои маро истифода бурда, маро ба омӯзиши мураккабии он ва сохтани ҳалли самараноки TypeScript водор кард. Ин мақола танҳо дар бораи гузаронидани мусоҳибаҳои кодингӣ нест (гарчанде ки ин як фоидаи хуб аст). Ин дар бораи шодмонии ҳалли мушкилот, ҳаяҷони оптимизатсия ва зебоии зебои рамзи самаранок аст. Ва азбаски ман каме математикдорам, мо ҳатто ба асосҳои математикии ҳалл ҳамчунин ғарқ мешавем.

Мушкилот: Гург дар либоси гӯсфанд

Мушкилот як маҷмӯи тартибнаёфтаи ададҳои пурраро пешниҳод мекунад. Вазифаи шумо: хурдтарин рақами мусбати гумшударо ёбед. Ба назар сода менамояд? Боз фикр кунед. Маҳдудиятҳои вақти O(n) ва мураккабии фазои O(1) ин вазифаи ба назар содаро ба як муаммои алгоритмии мушкил табдил медиҳанд.

Мушкилоти аввал: Доми қувваи бегона

Кӯшишҳои аввалини ман аз тартиб додан (вайрон кардани маҳдудияти вақти O(n)) ва маҷмӯаҳои хеш (зиёд кардани маҳдудияти фазои O(1)) иборат буданд. Ба таври равшан, як роҳи мураккабтар лозим буд.

Лаҳзаи "Эврика": Табдили дар ҷой

Тафоҳуми асосӣ дар он буд, ки ман метавонам массивҳои воридро ҳамчун ҷадвали хеш истифода барам. Бо тартиб додани элементҳо, ман метавонам рақами x-ро дар индекси x - 1 ҷойгир кунам (агар 1 ≤ x ≤ n бошад, ки дар он n дарозии массив аст). Ин табдили дар ҷой роҳи ҳалли самаранокро мекушояд.

Такмули рамз: Дастаи TypeScript

Ин таърихи такмули рамзи ман аст, ки бо шарҳҳои муфассал ва фаҳмиши математикӣ:

Версияи 1: Роҳи сода (бо ивазкуниҳои такроршаванда)

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

  // Ҳар рақамро дар мавқеи дурусти худ ҷойгир кунед, агар он дар диапазони [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]] // Иваз кардан
    }
  }

  // Аввалин рақами мусбати гумшударо пайдо кунед
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // Агар ҳама рақамҳо дар мавқеи дурусти худ бошанд, рақами гумшуда n + 1 аст
  return n + 1
}

Ин версия, гарчанде ки функсионалӣ аст, аз ивазкуниҳои такроршаванда ранҷ мебарад. Шумораи ивазкуниҳо дар ҳолати бадтарин ба O(n²) наздик мешавад, гарчанде ки ҳолати миёна ба O(n) наздиктар аст.

Шарҳ:

1. Тартиб додани массив: Ҳар рақами nums[i] дар индекси "дурусти" худ (nums[i] - 1) ҷойгир карда мешавад, агар он дар диапазони [1, n] бошад ва аллакай дар мавқеи дуруст набошад.

2. Муайян кардани рақами мусбати гумшуда: Пас аз тартиб додан, индекси аввалини i, ки дар он nums[i] !== i + 1 аст, нишон медиҳад, ки i + 1 рақами мусбати гумшуда аст.

3. Баргардонидани n + 1 агар лозим бошад: Агар ҳама рақамҳо аз 1 то n дар мавқеи дурусти худ бошанд, рақами гумшуда n + 1 аст.

Нуктаҳои асосӣ:

• Тартиб додани дар ҷой: Мо массив худро тағйир медиҳем, то аз истифодаи фазои иловагӣ худдорӣ кунем.
• Самаранокӣ: Ҳам тартиб додан ва ҳам скани ниҳоӣ вақти O(n)-ро мегирад, ки самаранокии оптималӣро таъмин мекунад.

Версияи 2: Афзоиши самаранокӣ (бекор кардани ивазкуниҳои такроршаванда)

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], nums[idx]]
    } else {
      idx++
    }
  }

  // Аввалин рақами мусбати гумшударо муайян кунед
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

Шарҳ:

1. Тартиб додани самаранок:

   • Давраи while элементҳоро бевосита ба мавқеи дурусти худ (nums[idx] - 1) танҳо вақте иваз мекунад, ки рақам дар диапазони дурусти [1, n] бошад ва аллакай дар мавқеи дурусти худ набошад.
   • Шарт if таъмин мекунад, ки рақамҳои нодуруст ё аллакай дуруст бе ивазкуниҳои ғайрилозимӣ гузашта мешаванд.

2. Санҷиши индекси бевосита:

   • Дар давраи тартиб додан, ивазкуниҳои нодуруст ва амалиётҳои такроршаванда бо тафтиши диапазон ва арзиши nums[idx] пешгирӣ карда мешаванд.

3. Иваз кардани босамара аз рӯи хотира:

   • Истифодаи деструктуринг ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) барои тағйирёбандаи муваққатӣ зарурат надорад, ки истифодаи хотираро кам мекунад.

4. Давраҳои камтар:

   • Алгоритм танҳо ду гузариши хаттӣ истифода мебарад:
     • Яке барои тартиб додани массив дар ҷой.
     • Дигаре барои ёфтани аввалин рақами мусбати гумшуда.

Таҳлили мураккабӣ:

• Мураккабии вақт:
  • Давраи while ва давраи for ҳарду дар O(n) иҷро мешаванд, ки мураккабии умумии вақтро O(n) месозад.
• Мураккабии фазо:
  • Алгоритм дар ҷой кор мекунад, бидуни истифодаи ягон сохтори маълумоти ёрирасон, бинобар ин мураккабии фазо O(1) аст.

Чаро ин рамз оптималӣ аст:

• Самаранокӣ: Давраи while-и соддашуда амалиётҳои такроршавандаи камтарро таъмин мекунад, ки суръати максималӣро таъмин мекунад.
• Самаранокии хотира: Истифодаи ивазкунии дар ҷой ва пешгирии тағйирёбандаҳои иловагӣ камтарин фазои хотираро таъмин мекунад.

Версияи 3: Оптимизатсияшуда барои хотира (камтарин истифодаи фазо)

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
}

Оптимизатсияҳои асосии хотира:

1. навсозиҳои дар ҷой бо тағйирёбандаҳои муваққатии камтар:

   • Ба ҷои истифодаи тағйирёбандаи temp барои иваз кардан, ин рамз массивҳоро бевосита бо nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1 тағйир медиҳад.
   • Ин барои тағйирёбандаи муваққатӣ зарурат надорад, ки сарбории хотираро бо миқдори доимӣ кам мекунад.

2. Арзишҳои муваққатии камтар дар давра:

   • Рамз correctIdx-ро бевосита дар давра ҳисоб мекунад, ки барои нигоҳ доштани тағйирёбандаҳои миёнаи иловагӣ дар берун аз мантиқи асосӣ зарурат надорад.
   • Таъиноти тағйирёбандаҳои камтар маънои истифодаи хотираи каме камтарро дар ҳар як такрор дорад.

3. Гузариши ягона барои тартиб додан:

   • Бар хилофи рамзи аввал, ки шартҳои зинадорро дар давраи while истифода мебарад, ин татбиқ ивазкуниҳоро анҷом медиҳад ё индекси пешрафтаро бо роҳи самараноктар анҷом медиҳад, ки чуқурии рӯйхати иҷро ва истифодаи хотираро кам мекунад.
   • Сохтори давра (while бо як афзоиш ё тартиб додани ягона) бештар мустақим аст, ки ба арзишҳои ёрирасони камтар ниёз дорад.

4. Санҷишҳои такроршаванда нест:

   • Санҷишҳо барои correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] мухтасар мебошанд ва амалиётҳои ғайрилозимиро пешгирӣ мекунанд, ки метавонанд муваққатан хотираи Stack ё CPU cache-ро истифода баранд.
   • Ин аз зарурати ҷудо кардани захираҳои иловагӣ барои амалиётҳое, ки ба натиҷа мусоидат намекунанд, пешгирӣ мекунад.

Чаро ин дар хотира тағйирот меорад:

• Кам кардани нигоҳдории муваққатӣ: Бо такя накардан ба тағйирёбандаи temp ва кам кардани ҳисоббарориҳои миёна, фазои хотира хурдтар аст.
• Иҷрои соддашуда: Марҳилаҳои камтар ва мантиқи соддатар ба истифодаи камтари хотира дар ҳар амалиёт табдил меёбад.
• Истифодаи беҳтариши Cache: Намунаи дастрасии хаттии пешбининашавандаи алгоритм самаранокии Cache-и CPU-ро беҳтар мекунад, ки ба таври ғайримустақим сарбории хотираро кам мекунад.

Ин ҳалли масъала ба навсозиҳои бевоситаи дар ҷой, истифодаи тағйирёбандаҳои кам ва намунаҳои дастрасии самараноки хотира такя мекунад, ки онро аз ҷиҳати самаранокии хотира беҳтарин месозад. Гарчанде ки сарфаҳо доимӣ мебошанд (O(1)), онҳо барои сабт шудан дар платформаҳои рақобатии мисли LeetCode, махсусан барои маълумотҳои калон кофӣ мебошанд.

Версияи 4: Асари шоҳкори оптимизатсияшуда (ивазкунии дар ҷой, бе 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
}

Ин версияи ниҳоӣ ҳам самаранокии оптималӣ ва ҳам истифодаи минималии хотираро тавассути ивазкунии зебои дар ҷой бидуни тағйирёбандаи муваққатӣ ба даст меорад. Мураккабии вақт ҳоло сахт O(n) аст ва мураккабии фазо O(1) аст, ки ҳамаи талаботро қонеъ мекунад. Аз ҷиҳати математикӣ, мо як навъ тағйироти даврӣ дар дохили массив барои ҷойгир кардани элементҳо дар мавқеи "дурусти" худ иҷро мекунем.

Бо илова кардани санҷиш (nums[i] === nums[nums[i] - 1]), мо ивазкуниҳои ғайрилозимиро пешгирӣ мекунем. Ин самаранокиро ба таври назаррас беҳтар мекунад ва мураккабии вақтро ба O(n)-и дилхоҳ наздиктар меорад.

Фарқиятҳои асосӣ дар татбиқ:

1. Пешгирии ивазкуниҳои такроршаванда:

   • Рамзи пешниҳодшуда ба таври возеҳ тафтиш мекунад, ки оё nums[i] === nums[nums[i] - 1] пеш аз иҷрои ивазкунӣ. Ин ивазкуниҳои ғайрилозимиро пешгирӣ мекунад, вақте ки рақам аллакай дар мавқеи дуруст аст ё нусхаҳо мавҷуданд.
   • Дар татбиқи аввал, ин санҷиш гузаронида намешавад, ки эҳтимолан ба ивазкуниҳои такроршаванда ҳатто вақте ки ғайрилозимӣ бошад, оварда мерасонад. Ҳар як ивазкунии иловагӣ сарборӣ меофарад, махсусан барои массивҳои калон.

2. Муқоисаи индекси бевосита:

   • Рамзи пешниҳодшуда while (nums[i] !== i + 1)-ро истифода мебарад, то боварӣ ҳосил кунад, ки рақам такроран ба мавқеи дурусти худ иваз карда мешавад, то он даме ки он дуруст ҷойгир карда шавад ё шароити нодуруст ба вуҷуд ояд. Ин такрори давраҳои ғайрилозимиро бартараф мекунад.
   • Рамзи аввал рақамро ба индекси пешбинишудаи худ дар шароити давра муқоиса намекунад. Он метавонад амалиётҳои бештарро дар ҳолатҳое, ки рақамҳо ба ҳаракати минималӣ ниёз доранд, иҷро кунад.

3. Санҷишҳои шартии оптимизатсияшуда:

   • Бо якҷоя кардани шартҳо дар як блоки if (масалан, nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]), рамз аз сарбории иловагӣ аз санҷишҳо ё ҳисоббарориҳои ғайрилозимӣ пешгирӣ мекунад.

Чаро ин дар LeetCode муҳим аст:

• Доимии вақти иҷро:

  • Ченкунии вақти иҷрои LeetCode метавонад ба амалиётҳои ғайрилозимӣ, ба монанди ивазкуниҳои такроршаванда ё муқоисаҳои иловагӣ ҳассос бошад.
  • Рамзи пешниҳодшуда ин амалиётҳоро кам мекунад, ки ба миёна суръати тезтар меорад.

• Самаранокии Cache:

  • Ивазкуниҳои камтар ва мантиқи давраи соддатар ба истифодаи беҳтари Cache-и CPU оварда мерасонад. Протсессорҳои муосир аз намунаҳои дастрасии пешбининашаванда ва соддашуда манфиат мебаранд, ки рамзи пешниҳодшуда нишон медиҳад.

Натиҷаҳо

Ин ҷадвал ҷамъбаст дар шакли ҷадвали пешниҳодшуда аст:

Ин ҷадвал савдо ва оптималии ҳалли ниҳоиро нишон медиҳад.

Хулоса нишон медиҳад, ки кӯшиши барои беҳтарин самаранокӣ ва хотира воқеан оптимизатсияшудатар аст, ки ба даст овардааст:

• Вақти иҷрои 1 ms: Мувофиқати тезтарин натиҷа аз ҷиҳати самаранокӣ.
• Истифодаи хотираи 58.9 MB: Каме баландтар аз нусхаи "беҳтарин хотира" (58.5 MB), вале пасттар аз дигар кӯшишҳо.

Таҳлил:

1. Вақти иҷро:

   • Вақти иҷрои 1 ms нишон медиҳад, ки роҳи оптимизатсияшуда санҷишҳои такроршаванда ва ивазкуниҳои ғайрилозимиро бартараф мекунад.
   • Мураккабии доимии вақти O(n) масштабпазириро барои маълумотҳои калон таъмин мекунад.

2. Хотира:

   • 58.9 MB рақобаткунанда аст ва нишон медиҳад, ки фазои хотира паст аст, ҳарчанд иҷро зуд аст. Ин афзоиши каме нисбат ба "беҳтарин хотира" (58.5 MB) метавонад аз фарқиятҳо дар деструктуринг ё оптимизатсияҳои мушаххаси муҳаррик бошад.

3. Савдо:

   • Ҳалли "беҳтарин хотира" каме вақти иҷроро барои истифодаи хотираи камтар фидо мекунад.
   • Ҳалли "беҳтарин самаранокӣ" бештар ба суръат диққат медиҳад, вале каме бештар хотира истифода мебарад.

Хулоса:

Ҳалли оптимизатсияшуда мувозинаи хубро таъмин мекунад:

• Вақти иҷрои 1 ms ба монанди рамзи беҳтарин иҷрошаванда тез аст.
• Истифодаи хотираи 58.9 MB ба натиҷаи беҳтарини хотира наздик аст, бо сарбории ночиз.

Ин интихоби хуб аст, махсусан барои ҳолатҳое, ки ҳам самаранокӣ ва ҳам хотира муҳиманд.

Асосҳои математикӣ: Тағйироти даврӣ ва принсипи кабутархона

Фикри асосӣ дар бораи мафҳуми тағйироти даврӣ мегардад. Мо кӯшиш мекунем, ки як давра эҷод кунем, ки дар он ҳар як рақами x дар индекси x - 1 ҷойгир карда шавад. Давраи while ин давраҳоро самаранок мегузаронад ва таъмин мекунад, ки ҳар як элемент ҷойи муайяншудаи худро пайдо мекунад.

Принсипи кабутархона дар ин ҷо нақши пинҳонӣ мебозад. Азбаски мо n мавқеи имконпазир дорем (индексҳои 0 то n-1) ва мо барои рақами мусбати гумшуда дар диапазони [1, n+1] меҷӯем, агар ҳама рақамҳо аз 1 то n мавҷуд бошанд, рақами гумшуда бояд n + 1 бошад.

Машғулият идома дорад...

Мафтунияти ман ба LeetCode 41 боқӣ мемонад. Ман доимо барои оптимизатсияҳои минбаъда ва фаҳмиши амиқтар меҷӯям. Ба ман дар ин ҷустуҷӯ ҳамроҳ шавед! Фикрҳои худро, ҳалли худатонро мубодила кунед ва биёед якҷоя буриши зебои математика ва алгоритмҳоро омӯзем.