زما د لیټ کوډ 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^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) وخت نیسي، د غوره فعالیت تضمینوي.

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

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 لوپ ډاډ ورکوي چې لږ اضافي عملیات شتون لري، سرعت زیاتوي.
• د حافظې موثریت: د په ځای تبادلې او د اضافي متغیرونو څخه ډډولو کارول ډاډ ورکوي چې تر ټولو ټیټ ممکنه حافظه پښه شتون لري.

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

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))، دوی په سیالي پلیټ فارمونو لکه لیټ کوډ کې ثبت کولو لپاره کافي مهم دي، په ځانګړې توګه د لوی ډاټا سیټونو لپاره.

نسخه ۴: غوره شاهکار (په ځای تبادله، هیڅ ټیمپ نه)

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]), کوډ د غیر ضروري چیکونو یا محاسبو څخه د اضافي اضافه کولو مخنیوی کوي.

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

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

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

• د کش موثریت:

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

پایلې

دلته په جدول بڼه کې وړاندې شوی خلاصه ده:

دا جدول سوداګرۍ او د وروستي حل د غوره کولو ښیي.

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

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

تحلیل:

1. رنټایم:

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

2. حافظه:

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

3. سوداګرۍ:

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

پایله:

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

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

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

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

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

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

جذبه دوام لري...

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