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

مسئله‌ی "اولین عدد مثبت گمشده" در لِت‌کد (شماره ۴۱) به آخرین وسواس برنامه‌نویسی من تبدیل شده است. این یک معما به‌ظاهر ساده است که ذهن مرا به خود مشغول کرده و مرا به کاوش در پیچیدگی‌های آن و ساخت کارآمدترین راه‌حل ممکن در تایپ‌اسکریپت سوق داده است. این پست فقط در مورد قبولی در مصاحبه‌های برنامه‌نویسی نیست (اگرچه این یک امتیاز خوب است). این در مورد لذت خالص حل مسئله، هیجان بهینه‌سازی و زیبایی ظریف کد کارآمد است. و از آنجایی که من کمی دیوانه‌ی ریاضی هستم، حتی به مبانی ریاضی راه‌حل نیز خواهیم پرداخت.

مسئله: گرگی در لباس میش

این مسئله آرایه‌ای نامرتب از اعداد صحیح را ارائه می‌دهد. وظیفه‌ی شما: یافتن کوچک‌ترین عدد صحیح مثبت گمشده. به‌نظر ساده می‌رسد؟ دوباره فکر کنید. محدودیت‌های زمان $O(n)$ و فضای $O(1)$ این کار به‌ظاهر ساده را به یک پازل الگوریتمی چالش‌برانگیز تبدیل می‌کند.

تلاش‌های اولیه: دام روش آزمون و خطا

تلاش‌های اولیه‌ی من شامل مرتب‌سازی (نقض محدودیت زمانی $O(n)$ ) و مجموعه‌های هش (تجاوز از محدودیت فضای $O(1)$ ) بود. واضح است که به رویکردی پیچیده‌تر نیاز بود.

لحظه‌ی یافتن راه حل: تبدیل درجا

بینش کلیدی این بود که می‌توانم از خود آرایه‌ی ورودی به عنوان یک جدول هش استفاده کنم. با تغییر مکان عناصر، می‌توانم عدد $x$ را در اندیس $x - 1$ قرار دهم (اگر $1 \le x \le 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)$ نزدیک‌تر است.

توضیح:

تغییر مکان آرایه: هر عدد 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)$ ) هستند، برای پلتفرم‌های رقابتی مانند لِت‌کد، به‌ویژه برای مجموعه‌های داده‌ی بزرگ، به اندازه‌ی کافی قابل توجه هستند.

نسخه ۴: شاهکار بهینه‌سازی‌شده (تعویض درجا، بدون متغیر موقت)

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 می‌شود. پردازنده‌های مدرن از الگوهای دسترسی قابل پیش‌بینی و ساده‌شده بهره می‌برند که کد ارائه شده از آن برخوردار است.

نتایج

در اینجا خلاصه‌ای که در قالب جدول ارائه شده است، آمده است:

تلاش	زمان اجرا	استفاده از حافظه	یادداشت‌ها
۴ (بهینه‌سازی‌شده)	۱ میلی‌ثانیه	۵۸٫۸ مگابایت	بهترین تعادل عملکرد و حافظه.
۳ (بهترین حافظه)	۲ میلی‌ثانیه	۵۸٫۵ مگابایت	کمی کندتر اما استفاده‌ی کمتر از حافظه.
۲ (بهترین عملکرد)	۱ میلی‌ثانیه	۵۸٫۹ مگابایت	زمان اجرای سریع‌تر.
۱ (تلاش اولیه)	۳ میلی‌ثانیه	۶۰ مگابایت	کندترین و بالاترین استفاده از حافظه.

این جدول، معاوضه‌ها و بهینگی راه‌حل نهایی را برجسته می‌کند.

خلاصه نشان می‌دهد که تلاش برای بهترین عملکرد و حافظه در واقع بهینه‌ترین است و به موارد زیر دست می‌یابد:

زمان اجرای ۱ میلی‌ثانیه: مطابق با سریع‌ترین نتیجه از نظر عملکرد.
استفاده از حافظه‌ی ۵۸٫۹ مگابایت: کمی بالاتر از کپی "بهترین حافظه" (۵۸٫۵ مگابایت) اما کمتر از تلاش‌های دیگر.

تحلیل:

زمان اجرا:
- زمان اجرای ۱ میلی‌ثانیه نشان می‌دهد که رویکرد بهینه‌سازی‌شده از بررسی‌های تکراری و تعویض‌های غیرضروری جلوگیری می‌کند.
- پیچیدگی زمانی ثابت $O(n)$ مقیاس‌پذیری را برای مجموعه‌های داده‌ی بزرگتر تضمین می‌کند.
حافظه:
- ۵۸٫۹ مگابایت رقابتی است و نشان می‌دهد که ردپای حافظه علی‌رغم اجرای سریع، کم است. این افزایش جزئی نسبت به "بهترین حافظه" (۵۸٫۵ مگابایت) ممکن است به دلیل تفاوت در ساختارشکنی یا بهینه‌سازی‌های خاص موتور باشد.
معاوضه‌ها:
- راه‌حل "بهترین حافظه" کمی زمان اجرا را برای استفاده‌ی کمتر از حافظه فدا می‌کند.
- راه‌حل "بهترین عملکرد" بیشتر بر سرعت تمرکز دارد اما از حافظه‌ی کمی بیشتر استفاده می‌کند.

نتیجه‌گیری:

راه‌حل بهینه‌سازی‌شده تعادل خوبی برقرار می‌کند:

زمان اجرای ۱ میلی‌ثانیه به سرعت کد با بهترین عملکرد است.
استفاده از حافظه‌ی ۵۸٫۹ مگابایت به نتیجه‌ی بهترین حافظه نزدیک است، با سربار ناچیز.

این یک انتخاب همه‌جانبه است، به‌ویژه برای سناریوهایی که هم عملکرد و هم حافظه حیاتی هستند.

مبانی ریاضی: جایگشت‌های دوری و اصل لانه کبوتری

ایده‌ی اصلی در حول مفهوم جایگشت‌های دوری می‌چرخد. هدف ما ایجاد یک چرخه است که در آن هر عدد $x$ در اندیس $x - 1$ قرار می‌گیرد. حلقه‌ی while به طور مؤثر این چرخه‌ها را طی می‌کند و اطمینان حاصل می‌کند که هر عنصر جایگاه تعیین‌شده‌ی خود را پیدا می‌کند.

اصل لانه کبوتری به طور ظریفی در اینجا نقش دارد. از آنجایی که ما $n$ موقعیت ممکن (اندیس‌های $0$ تا $n-1$ ) داریم و به دنبال یک عدد صحیح مثبت گمشده در محدوده‌ی $[1, n+1]$ هستیم، اگر همه اعداد از ۱ تا $n$ وجود داشته باشند، عدد گمشده باید $n + 1$ باشد.

وسواس ادامه دارد...

علاقه‌ی من به لِت‌کد ۴۱ همچنان باقی است. من دائماً در جستجوی بهینه‌سازی‌های بیشتر و بینش‌های عمیق‌تر هستم. به من در این جستجو بپیوندید! افکار، راه‌حل‌های خودتان را به اشتراک بگذارید و بیایید تقاطع ظریف ریاضیات و الگوریتم‌ها را با هم کاوش کنیم.