هوسي بمسألة LeetCode 41: غوص عميق في لغز أول عدد صحيح موجب مفقود

مشكلة "أول عدد صحيح موجب مفقود" في LeetCode (الرقم 41) أصبحت آخر هواجسي في البرمجة. إنها لغز بسيط بشكل مخادع استحوذ على أفكاري، ودفعني لاستكشاف تعقيداته وصياغة الحل الأكثر كفاءة ممكنًا بلغة TypeScript. هذه المقالة ليست فقط حول اجتياز مقابلات الترميز (على الرغم من أن هذا ميزة لطيفة). بل هي حول متعة حل المشكلات، وإثارة التحسين، والجمال الأنيق للكود الفعال. ولأنني مهووس بعض الشيء بالرياضيات، فسوف نتعمق حتى في الأسس الرياضية للحل.

المشكلة: ذئب في ثياب حمل

تقدم المشكلة مصفوفة غير مرتبة من الأعداد الصحيحة. مهمتك: إيجاد أصغر عدد صحيح موجب مفقود. يبدو بسيطًا؟ فكر مرة أخرى. قيود وقت $O(n)$ ومساحة $O(1)$ تعقد هذه المهمة البسيطة ظاهريًا وتحولها إلى لغز خوارزمي صعب.

الصعوبات الأولية: فخ القوة الغاشمة

تضمنت محاولاتي الأولى الفرز (مخالفًا لقيود وقت $O(n)$) ومجموعات التجزئة (تتجاوز حد مساحة $O(1)$). من الواضح، كان هناك حاجة إلى نهج أكثر تطوراً.

لحظة الإلهام: التحويل في المكان

كانت الفكرة الرئيسية هي إدراك إمكانية استخدام مصفوفة الإدخال نفسها كجدول تجزئة. من خلال إعادة ترتيب العناصر، يمكنني وضع الرقم $x$ في الفهرس $x - 1$ (إذا كان $1 \le x \le n$، حيث $n$ هو طول المصفوفة). هذا التحويل في المكان يفتح الطريق لحل فعال.

تطور الكود: ملحمة TypeScript

فيما يلي سجل تطور الكود الخاص بي، مع تفسيرات مفصلة ورؤى رياضية:

الإصدار الأول: النهج الساذج (مع عمليات تبادل متكررة)

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] موجزة وتمنع العمليات غير الضرورية التي يمكن أن تستخدم مؤقتًا ذاكرة المُكدس أو ذاكرة التخزين المؤقت لوحدة المعالجة المركزية.
   • هذا يتجنب الحاجة إلى تخصيص موارد إضافية للعمليات التي لن تساهم في النتيجة.

لماذا هذا يُحدث فرقًا في الذاكرة:

• تقليل التخزين المؤقت: من خلال عدم الاعتماد على متغير temp وتقليل العمليات الحسابية الوسيطة، تصبح مساحة الذاكرة أصغر.
• تنفيذ مُحسّن: خطوات أقل ومنطق أبسط يعني استخدام ذاكرة أقل لكل عملية.
• استخدام ذاكرة التخزين المؤقت المحسّن: نمط الوصول الخطي والمتوقع للخوارزمية يحسن أداء ذاكرة التخزين المؤقت لوحدة المعالجة المركزية، مما يقلل بشكل غير مباشر من استخدام الذاكرة.

يركز هذا الحل على التحديثات المباشرة في المكان، واستخدام متغيرات ضئيلة، وأنماط الوصول إلى الذاكرة الفعالة، مما يجعله الأفضل من حيث كفاءة الذاكرة. على الرغم من أن المدخرات ثابتة ($O(1)$)، إلا أنها كبيرة بما يكفي لتسجيلها على منصات تنافسية مثل LeetCode، خاصةً بالنسبة لمجموعات البيانات الكبيرة.

الإصدار الرابع: التحفة المُحسّنة (التبادل في المكان، بدون متغير مؤقت)

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 حساسة للعمليات غير الضرورية، مثل عمليات التبادل المتكررة أو المقارنات الإضافية.
  • يقلل الكود المُقدّم من هذه العمليات، مما يؤدي إلى وقت تشغيل أسرع في المتوسط.

• كفاءة ذاكرة التخزين المؤقت:

  • عمليات التبادل الأقل ومنطق الحلقة الأبسط يؤديان إلى استخدام أفضل لـ ذاكرة التخزين المؤقت لوحدة المعالجة المركزية. تستفيد المعالجات الحديثة من أنماط الوصول المتوقعة والمنسابة، والتي يُظهرها الكود المُقدّم.

النتائج

فيما يلي ملخص مُقدّم في شكل جدول:

يُبرز هذا الجدول التبادلات التجريبية وأمثل الحل النهائي.

يشير الملخص إلى أن محاولة الأداء والذاكرة الأمثل هي بالفعل الأكثر تحسينًا، حيث تحقق:

• وقت تشغيل 1 مللي ثانية: مطابق لأسرع نتيجة من حيث الأداء.
• استخدام ذاكرة 58.9 ميجابايت: أعلى قليلاً من نسخة "أفضل ذاكرة" ولكن أقل من المحاولات الأخرى.

التحليل:

1. وقت التشغيل:

   • يُظهر وقت التشغيل 1 مللي ثانية أن النهج المُحسّن يلغي عمليات الفحص المتكررة وعمليات التبادل غير الضرورية.
   • يضمن تعقيد الوقت الثابت $O(n)$ قابلية التوسع لمجموعات البيانات الأكبر.

2. الذاكرة:

   • 58.9 ميجابايت تنافسية، مما يدل على أن مساحة الذاكرة منخفضة على الرغم من التنفيذ السريع. قد يكون هذا الارتفاع الطفيف عن "أفضل ذاكرة" (58.5 ميجابايت) بسبب اختلافات في التفكيك أو التحسينات الخاصة بالمحرك.

3. التبادلات:

   • يضحي حل "أفضل ذاكرة" قليلاً بوقت التشغيل مقابل استخدام ذاكرة أقل.
   • يركز حل "أفضل أداء" أكثر على السرعة ولكنه يستخدم ذاكرة أكبر قليلاً.

الخلاصة:

يحقق الحل المُحسّن توازنًا جيدًا:

• وقت تشغيل 1 مللي ثانية سريع مثل أفضل كود أداء.
• استخدام ذاكرة 58.9 ميجابايت قريب من أفضل نتيجة للذاكرة، مع عبء إضافي ضئيل.

إنه خيار شامل، خاصةً في السيناريوهات التي يكون فيها كل من الأداء والذاكرة أمرًا بالغ الأهمية.

الأسس الرياضية: الإزاحات الدورية ومبدأ الحمامة

تدور الفكرة الأساسية حول مفهوم الإزاحات الدورية. نهدف إلى إنشاء دورة حيث يتم وضع كل رقم $x$ في الفهرس $x - 1$. تقوم حلقة while فعليًا بعبور هذه الدورات، مما يضمن أن كل عنصر يجد مكانه المخصص.

يلعب مبدأ الحمامة دورًا خفيًا هنا. بما أن لدينا $n$ موضعًا ممكنًا (الفهرس من $0$ إلى $n-1$) ونحن نبحث عن عدد صحيح موجب مفقود ضمن النطاق $[1، n+1]$، إذا كانت جميع الأعداد من 1 إلى $n$ موجودة، فيجب أن يكون العدد المفقود هو $n + 1$.

الهوس مستمر...

يبقى إعجابي بـ LeetCode 41. أنا أسعى باستمرار إلى مزيد من التحسينات والرؤى الأعمق. انضم إليّ في هذه المهمة! شارك أفكارك، وحلولك الخاصة، دعنا نستكشف تقاطع الرياضيات والخوارزميات الأنيق معًا.