وسواس من به LeetCode 41: شیرجه عمیق به معما اولین عدد مثبت گمشده

د مسئلې "لومړی مثبت شمېره" (شمېره ۴۱) د لیټ کوډ په نوم د پروګرامینګ ویب پاڼې یوه مسئله ده چې په دې وروستیو کې زما د کوډینګ لپاره د زړه راښکونکي شیبې شوې دي. دا یوه ښکاره ساده پزل ده چې زما فکر یې نیولی دی او ما اړ کړی چې د هغې د پیچلتیاوو څرنګوالي او د ټایپ سکرپټ لپاره د تر ټولو موثر حل جوړولو په لټه کې شم. دا پوسټ یوازې د کوډینګ انټرویو په اړه نه دی (که څه هم دا یوه ښه ګټه ده). دا د ستونزې د حل کولو د خالص خوښۍ، د اصلاح کولو د هیجان او د اغیزمن کوډ د ښکلي ښکلا په اړه دی. او ځکه چې زه یو څه د ریاضیاتو مینه وال یم، موږ به حتی د حل د ریاضي بنسټونو ته هم ځای ورکړو.

ستونزه: په پړوني جامو کې وړوکي

ستونزه د انټیجرونو یو غیر منظم آری ارائه کوي. ستاسو دنده: تر ټولو کوچنی ورک شوی مثبت انټیجر ومومئ. ساده ښکاري؟ بیا فکر وکړئ. د O(n) وخت او O(1) ځای پیچلتیا قیدونه دا ښکاره ساده دنده په یوه ننګونکي الګوریتمیک پزل بدلوي.

لومړنۍ هڅې: د بروس فورس دام

زما لومړنۍ هڅې د ډلبندۍ (د O(n) وخت قید ماتول) او هش سیټونو (د O(1) ځای حد څخه زیاتول) په ګډون وې. په څرګنده توګه، یو ډیر پرمختللی تګلاره اړینه وه.

د یوریکا شیبه: د ځای په ځای بدلون

مفتاحي بصیرت دا وه چې پوه شوم چې زه کولی شم د انپټ آری په خپل ځان کې د هش ټیبل په توګه وکاروم. د عناصرو د بیار تنظیمولو له لارې، زه کولی شم شمېره x په شاخص x - 1 کې ځای پر ځای کړم (که 1 ≤ x ≤ n، چیرې چې n د آری اوږدوالی دی). دا د ځای په ځای بدلون د اغیزمن حل لاره خلاصوي.

د کوډ پرمختګ: د ټایپ سکرپټ سګا

دلته د زما د کوډ د پرمختګ تاریخ دی، د تفصيلي توضیحاتو او ریاضي بصیرتو سره:

نسخه ۱: ساده تګلاره (د زاید سوپونو سره)

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) ته نژدې دی.

تشریح:

۱. د آری بیا تنظیم کول: هره شمېره nums[i] په خپل "سم" شاخص (nums[i] - 1) کې ځای پر ځای کیږي که چیرې دا د [1، n] په رینج کې وي او لا دمخه په سمه موقعیت کې نه وي.

۲. د ورک شوي مثبت پیژندل: د بیا تنظیم کولو وروسته، لومړی شاخص i چیرې چې nums[i] !== i + 1 ښیي چې i + 1 ورک شوی مثبت انټیجر دی.

۳. که اړتیا وي n + 1 بیرته راګرځوئ: که ټولې شمېرې له 1 څخه تر n پورې په سمو موقعیتونو کې وي، ورک شوی شمېره n + 1 ده.

مهم ټکي:

• د ځای په ځای بیار تنظیم کول: موږ آری په خپل ځان کې تعدیل کوو ترڅو د اضافي ځای کارولو څخه مخنیوی وکړو.
• موثریت: د بیار تنظیم کولو او وروستي سکین دواړه د O(n) وخت نیسي، د غوره فعالیت تضمینوي.

نسخه ۲: د فعالیت زیاتوالی (د زاید سوپونو له منځه وړل)

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
}

تشریح:

۱. موثره بیار تنظیم کول:

• while لوپ عناصر په مستقیم ډول په خپلو سمو موقعیتونو (nums[idx] - 1) کې تبادله کوي یوازې کله چې شمېره د [1، n] په معتبر رینج کې وي او لا دمخه په خپل سمه موقعیت کې نه وي.
• if شرط ډاډ ورکوي چې غیر معتبر یا لا دمخه سمې شمېرې د غیر ضروري سوپونو پرته له پامه غورځول کیږي.

۲. مستقیم شاخص چیک کول:

• د بیا تنظیم کولو پړاو په جریان کې، د nums[idx] د رینج او ارزښت د چیک کولو له لارې د غیر معتبر سوپونو او زاید عملیاتو څخه مخنیوی کیږي.

۳. د حافظې اغیزمن تبادله:

• د ډیسټراکچرینګ کارول ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]) د لنډمهاله متغیر اړتیا له منځه وړي، د حافظې کارول کموي.

۴. لږ لوبونه:

• الګوریتم یوازې دوه لینر پاسونه کاروي:
  • یو د آری د ځای په ځای بیا تنظیم کولو لپاره.
  • بل د لومړي ورک شوي مثبت موندلو لپاره.

پیچلتیا تحلیل:

• د وخت پیچلتیا:
  • while لوپ او for لوپ دواړه په O(n) کې چلیږي، د ټول وخت پیچلتیا O(n) جوړوي.
• د ځای پیچلتیا:
  • الګوریتم د کومې مرستندویه ډاټا جوړښتونو پرته په ځای کې عملیات کوي، نو د ځای پیچلتیا O(1) ده.

ولې دا کوډ غوره دی:

• کارکردګي: ساده شوی while لوپ ډاډ ورکوي چې لږ زاید عملیات شتون لري، سرعت اعظمي کوي.
• د حافظې موثریت: د ځای په ځای تبادلې کارول او د اضافي متغیرونو څخه مخنیوی ډاډ ورکوي چې تر ټولو ټیټ ممکنه حافظه شتون لري.

نسخه ۳: د حافظې لپاره غوره شوې (لږ تر لږه ځای کارول)

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
}

د حافظې کلیدي اصلاحات:

۱. د لږ تر لږه لنډمهاله متغیرونو سره د ځای په ځای تازه کول:

• د تبادلې لپاره د temp متغیر کارولو پرته، دا کوډ په مستقیم ډول آری د nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1 سره تعدیل کوي.
• دا د لنډمهاله متغیر اړتیا له منځه وړي، د حافظې سربار په یوه ثابته اندازه کموي.

۲. په لوپ کې لږ لنډمهاله ارزښتونه:

• کوډ په مستقیم ډول په لوپ کې correctIdx محاسبه کوي، د منطق له بهر د اضافي منځني متغیرونو ذخیره کولو اړتیا له منځه وړي.
• لږ متغیر ټاکنې پدې مانا دي چې د هر تکرار لپاره د حافظې کارول یو څه کم دي.

۳. د بیار تنظیم کولو لپاره واحد پاس:

• د لومړي کوډ په څیر چې په while لوپ کې د نیسټ شوي شرایطو کاروي، دا پلي کول سوپس بشپړوي یا شاخص په ډیر ساده ډول مخ ته ځي، د رنټایم سټیک ژوروالی او د حافظې کارول کموي.
• د لوپ جوړښت (while د یو واحد زیاتوالي یا بیار تنظیم کولو سره) ډیر مستقیم دی، د لږ مرستندویه ارزښتونو اړتیا لري.

۴. هیڅ زاید چیکونه:

• د correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] چیکونه مختصر دي او د غیر ضروري عملیاتو څخه مخنیوی کوي چې کولی شي په موقتي ډول د سټیک یا CPU کش حافظه وکاروي.
• دا د اضافي سرچینو د ټاکلو اړتیا له منځه وړي د عملیاتو لپاره چې پایلې ته به هیڅ مرسته ونه کړي.

ولې دا د حافظې په اړه توپیر رامنځته کوي:

• کم شوی لنډمهاله ذخیره کول: د temp متغیر ته د تکیه کولو پرته او د منځنیو محاسبو کمولو له لارې، د حافظې ټاپه کوچنۍ ده.
• ساده شوې اجرا: لږ ګامونه او ساده منطق په هر عملیات کې د حافظې کارول کموي.
• د کش کارولو ښه والی: د الګوریتم لینر، وړاندوینې وړ لاسرسي الگو د CPU کش فعالیت ښه کوي، په غیر مستقیم ډول د حافظې سربار کموي.

د مستقیم ځای په ځای تازه کولو، لږ متغیر کارولو او د حافظې د مؤثره لاسرسي نمونو باندې د دې حل تمرکز یې د حافظې اغیزمنتوب په لحاظ غوره کوي. پداسې حال کې چې سپمونه ثابت دي (O(1))، دوی دومره مهم دي چې د لیټ کوډ په څیر سیالي پلیټ فارمونو کې ثبت شي، په ځانګړي توګه د لویو ډاټا سیټونو لپاره.

نسخه ۴: غوره شوی شاهکار (د ځای په ځای تبادله، هیڅ 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) ته راوړي.

د پلي کولو کليدي توپیرونه:

۱. د زاید سوپونو څخه مخنیوی کول:

• چمتو شوی کوډ په صریح ډول چیک کوي که nums[i] === nums[nums[i] - 1] وي مخکې له دې چې تبادله ترسره کړي. دا د غیر ضروري سوپونو څخه مخنیوی کوي کله چې شمېره لا دمخه په سمه موقعیت کې وي یا ډبلونه شتون ولري.
• په لومړي پلي کولو کې، دا چیک له پامه غورځول شوی، ممکن د غیر ضروري سوپونو لامل شي. هر اضافي تبادله سربار اضافه کوي، په ځانګړي توګه د لویو آریونو لپاره.

۲. د مستقیم شاخص پرتله کول:

• چمتو شوی کوډ while (nums[i] !== i + 1) کاروي ترڅو ډاډ ترلاسه کړي چې شمېره په دوامداره توګه په خپل سمه موقعیت کې تبادله کیږي تر هغه چې دا په سمه توګه ځای پر ځای شي یا یو غیر معتبر حالت پوره شي. دا د غیر ضروري لوپ تکرارونه له منځه وړي.
• لومړی کوډ په لوپ حالت کې شمېره په خپل ارادي شاخص سره په صریح ډول نه پرتله کوي. دا کولی شي په هغو مواردو کې ډیر عملیات ترسره کړي چیرې چې شمېرو ته لږ حرکت ته اړتیا وي.

۳. غوره شوي مشروط چیکونه:

• د شرایطو د یو واحد if بلاک کې (nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]) په یوځای کولو سره، کوډ د غیر ضروري چیکونو یا محاسبو څخه اضافي سربار له منځه وړي.

ولې دا په لیټ کوډ کې مهم دی:

• د رنټایم ثبات:

  • د لیټ کوډ د رنټایم اندازه کول کولی شي د غیر ضروري عملیاتو، لکه زاید سوپونه یا اضافي پرتله کول، حساس وي.
  • چمتو شوی کوډ دا عملیات کموي، په اوسط ډول ګړندی رنټایم راوړي.

• د کش موثریت:

  • لږ سوپونه او ساده لوپ منطق د CPU کش کارولو ښه والی راوړي. عصري پروسیسرونه د وړاندوینې وړ او ساده شویو لاسرسي نمونو څخه ګټه پورته کوي، کوم چې چمتو شوی کوډ ښیي.

پایلې

دلته په جدول بڼه کې راغلي خلاصه ده:

دا جدول د سوداګرۍ او د وروستي حل د غوره والي څرګندوي.

خلاصه ښیي چې د غوره فعالیت او حافظې لپاره هڅه په حقیقت کې تر ټولو غوره ده، چې ترلاسه کوي:

• ۱ ms رنټایم: د فعالیت په لحاظ تر ټولو ګړندي پایلې سره سمون لري.
• ۵۸.۹ MB د حافظې کارول: د "غوره حافظې" کلون څخه یو څه لوړ خو د نورو هڅو څخه ټیټ.

تحلیل:

۱. رنټایم:

• ۱ ms رنټایم ښیي چې غوره شوې تګلاره د زاید چیکونو او غیر ضروري سوپونو څخه مخنیوی کوي.
• د O(n) منظم وخت پیچلتیا د لویو ډاټا سیټونو لپاره پیمانه کول تضمینوي.

۲. حافظه:

• ۵۸.۹ MB سیالي ده، ښیي چې د حافظې ټاپه د ګړندي اجرا سره سره ټیټه ده. دا د "غوره حافظې" (۵۸.۵ MB) په پرتله لږ ډیریدل ممکن د ډیسټراکچرینګ یا انجن مشخص اصلاحاتو له امله وي.

۳. سوداګرۍ:

• د "غوره حافظې" حل د ټیټ حافظې کارولو لپاره رنټایم یو څه قرباني کوي.
• د "غوره فعالیت" حل ډیر په سرعت تمرکز کوي خو marginally ډیره حافظه کاروي.

پایلې:

غوره شوی حل ښه توازن رامنځته کوي:

• ۱ ms رنټایم د غوره فعالیت کوډ په څیر ګړندی دی.
• ۵۸.۹ MB د حافظې کارول د غوره حافظې پایلو ته نژدې دي، د ناچپه سربار سره.

دا یو ښه ټاکل شوی انتخاب دی، په ځانګړي توګه د هغو سناریو لپاره چیرې چې دواړه فعالیت او حافظه مهم دي.

ریاضي بنسټونه: سایکلیک بدلونونه او پیجن هول اصول

مفتاحي نظر د سایکلیک بدلونونو مفهوم په شاوخوا کې څرخي. موږ هڅه کوو چې یو سایکل جوړ کړو چیرې چې هره شمېره x په شاخص x - 1 کې ځای پر ځای شي. while لوپ په مؤثره توګه د دغو سایکلونو څخه تیریږي، ډاډ ورکوي چې هر عنصر خپل ټاکل شوی ځای ومومي.

د پیجن هول اصل دلته په ناڅاپي ډول رول لوبوي. ځکه چې موږ د n ممکن موقعیتونه (شاخصونه ۰ تر n-۱) لرو او موږ د [۱، n+۱] په رینج کې د ورک شوي مثبت انټیجر په لټه کې یو، که ټولې شمېرې له ۱ څخه تر n پورې موجود وي، ورک شوی شمېره باید n + ۱ وي.

د شیبې دوام لري...

زما د لیټ کوډ ۴۱ سره مینه دوام لري. زه په دوامداره توګه د نورو اصلاحاتو او ژور بصیرتونو په لټه کې یم. زما سره په دې لټون کې یوځای شئ! خپل نظرونه، خپلې حلونه شریک کړئ، او راځئ چې د ریاضیاتو او الګوریتمونو د ښکلي تقاطع په ګډه وپلټو.