Obsesyona Min a LeetCode 41: Kûrveçûnek di Pirsgirêka Hejmara Erêniya Windabûyî de

پرسیارا "ژمارەى پۆزەتیڤى ونبوو" ya LeetCode (ژمارە 41) بووە بە هەڵواسراوەى کۆد نوسینى دوایینم. ئەمە پرسیارێکى سادە و فێڵبازە کە بیرەکانی منی داگیر کردووە و رێگەى پێداوم بۆ لێکۆڵینەوە لە تایبەتمەندییەکانی و دروستکردنى باشترین چارەسەرى TypeScript کە هەیە. ئەم پۆستە تەنها باسى تێپەڕاندنى پشکنینەکانى کۆد نوسین نییە (هەرچەندە ئەمەش خاڵێکى باشە). باسى خۆشى چارەسەرکردنى کێشەکانە، هیجانى باشترکردن، و جوانیى شێوازى کۆدێکى کارا. و چونکە منیش کەمێک دڵسۆزى ماتماتیکم، ئێمە دەچینە ناو بنەماکانى ماتماتیکیى چارەسەرەکەشەوە.

کێشەکە: گرگێک لە پێستى مێشە!

ئەم کێشەیە رێزێکى نە رێکخراوى ژمارەکانى تەواو پێشکەش دەکات. ئەرکى تۆ: بچووکترین ژمارەى پۆزەتیڤى ونبوو بدۆزیتەوە. دەردەکەوێت راستەوخۆیە؟ جارێکى تر بیر بکەرەوە. سنوورەکانى کاتى $O(n)$ و شوێنى $O(1)$ ئەم ئەرکەى بەدیاریکراو دەگۆڕن بۆ پرسیارێکى ئەلگۆریتمیی دژوار.

تێکۆشانە سەرەتاییەکان: تەڵەکەى هێزى خاوێن

هەوڵە سەرەتاییەکانم بریتی بوون لە رێکخستن (سەرپێچیکردن لە سنوورى کاتى $O(n)$) و کۆمەڵەى هاش (تێپەڕاندنى سنوورى شوێنى $O(1)$). بەڕوونى، پێویستى بە رێبازێکى پێشکەوتووتری هەبوو.

چرکەى یوریکا: گۆڕینی شوێن

تێگەیشتنى سەرەکی ئەوە بوو کە دەتوانم خۆى رێزەکە بەکاربهێنم وەک جەدولێکى هاش. بە رێکخستنەوەى تەواوەکان، دەتوانم ژمارەى $x$ لە ڕیزى $x - 1$ دابنێم (ئەگەر $1 \le x \le 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^2)$، هەرچەندە حاڵەتى مامناوەندی نزیکە لە $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] کورت و ڕوونن و لەبەرچاو لادانى ئۆپەراسیۆنەکانى پێویست ناکەن کە دەتوانن بە کاتی بیرگەى ستاک یان کەشی CPU بەکاربهێنن.
   • ئەمە لە بەرچاو لادانى پێویستى بە سەرچاوە زیادە بۆ ئۆپەراسیۆنەکان کە بەشداری لە ئەنجامدا ناکەن.

هۆکارى ئەوەى کە ئەمە لە بیرگەدا جیاوازى دەکات:

• کەمکردنەوەى پاراستنى کاتی: بە پشت نەبەستن بە گۆڕێکى temp و کەمکردنەوەى حسابەکانى ناوەندى، پێدانی بیرگە کەمترە.
• جێبەجێکردنى باشترکراو: هەنگاوەکانى کەمتر و لۆجیکى سادەتر دەگۆڕێن بۆ بەکارهێنانى بیرگەى کەمتر لە هەر ئۆپەراسیۆنێک.
• بەکارهێنانى باشترى کەش: شێوازى دەستپێکردنى ڕاستەوخۆ و پێشبینی کراوى ئەلگۆریتەم بەکارهێنانى کەشى CPU باشتر دەکات، بە نێرراوە کەمکردنەوەى بەکارهێنانى بیرگە.

ئەم چارەسەرەى سەرنجدانی راستەوخۆى لە شوێنى خۆیدا، کەمترین بەکارهێنانى گۆڕ، و شێوازە کارایەکانى دەستپێکردنى بیرگە، باشترینە لەڕووى کارایى بیرگەوە. هەرچەندە پاراستنەکان هەمیشەیین ($O(1)$)، بەڵام بەسە بۆ تۆمارکردن لە پلاتفۆرمەکانی وەک LeetCode، بە تایبەت بۆ داتاکانى گەورە.

وێرژنی 4: شاکارى باشترکراو (گۆڕینەوەى لە شوێنى خۆیدا، بێ گۆڕى کاتی)

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 دەتوانێت هەستیار بێت بەرامبەر ئۆپەراسیۆنەکانى زیادە، وەک گۆڕینەوەکانى زێدە یان بەراوردەکانى زیادە.
  • کۆدى پێشکەشکراو ئەم ئۆپەراسیۆنانە کەم دەکاتەوە، بۆ کاتێکى خێراتر بە مامناوەندى.

• کارایى کەش:

  • گۆڕینەوەکانى کەمتر و لۆجیکى سادەترى لەوپەر ئەنجامێکى باشتر لە بەکارهێنانى کەشى 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 ماوەتەوە. بەردەوام لەگەڵ باشترکردنى زیاتر و تێگەیشتنى قوڵتر دەگەڕێم. لەگەڵم بەشداری بکە لەم گەشتەدا! بیرەکانتان، چارەسەرەکانى تایبەتى خۆتان، و با لەگەڵ یەکتر لێکۆڵینەوە بکەین لە هاوبەندیی جوانى ماتماتیک و ئەلگۆریتمەکان.