First Missing Positive
لديك مصفوفة غير مرتبة من الأعداد الصحيحة nums. أعد أصغر عدد صحيح موجب (1 أو أكبر) لا يظهر في nums. قد تحتوي المصفوفة على أعداد سالبة وأصفار وقيم مكررة وقيم أكبر بكثير من طولها.
الدالة
- numsinteger-array
- الأعداد الصحيحة غير المرتبة، التي قد تتكرر وقد تكون سالبة أو صفرًا أو كبيرة جدًا
- تُرجعinteger
- أصغر عدد صحيح موجب غير موجود في nums
القيود
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- القيم ليست مرتبة بأي ترتيب معيّن، وقد تتكرر.
أمثلة
- المدخلات
- nums = [5, -2, 1, 3, 2, 9]
- المخرجات
- 4
- الشرح
- الأعداد 1 و2 و3 كلها موجودة في المصفوفة، أما 4 فليس موجودًا، لذا فالإجابة هي 4. ولا يهم العددان 5 و9 عند غياب قيمة أصغر.
- المدخلات
- nums = [4, 2, 1, 3]
- المخرجات
- 5
- الشرح
- تحتوي المصفوفة على كل قيمة من 1 إلى 4، لذا فإن أول قيمة تفتقدها هي 5، أي أكثر من طولها بواحد.
- المدخلات
- nums = [-1, 0, 6, 8]
- المخرجات
- 1
- الشرح
- -1 و0 ليسا موجبين، و6 و8 يتركان 1 دون تغطية، لذا فالإجابة هي 1.
سؤال إضافي
هل يمكنك إيجاد الإجابة في زمن O(n) مع استخدام ذاكرة إضافية O(1) فقط؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تحتوي المصفوفة ذات الطول n على n قيمة. ما أكبر قيمة ممكنة للإجابة؟ وما القيم في المصفوفة التي يمكنك تجاهلها بسبب ذلك؟
الإجابة لا تتجاوز n+1، لذا لا تهم سوى القيم من 1 إلى n. يكفي جدول من n أعلام لتسجيل القيم التي تظهر منها. تحتوي المصفوفة نفسها على n خانات بالضبط: فهل يمكن أن تؤدي دور هذا الجدول؟
تنتمي القيمة
vإلى الفهرسv-1. بدّل كل قيمة من 1 إلى n إلى خانتها، وواصل التبديل عند الفهرس نفسه حتى لا تكون للقيمة الموجودة هناك خانة أو تكون خانتها تحتوي بالفعل على القيمة نفسها. بعد ذلك، يكون أول فهرسiلا يحتوي علىi+1هو الإجابة، أو n+1 إذا كانت كل الخانات صحيحة.
الحل
يستغرق الترتيب زمنًا قدره O(n log n)، وتستهلك مجموعة التجزئة ذاكرة إضافية قدرها O(n). لكن هناك حدًا يتفوق على كليهما: تغطي n قيمةً على الأكثر n من الأعداد من 1 إلى n+1، لذا فإن الإجابة لا تتجاوز n+1. لا تهم سوى القيم من 1 إلى n، ولذا تحتوي المصفوفة على n خانة لتسجيلها، فتتراجع الذاكرة الإضافية إلى O(1).
جرّب كل مرشّح بإجراء مسح كامل
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
اختبر الأعداد المرشحة 1، 2، 3، ... بالترتيب. ولكل عدد مرشح، افحص المصفوفة كلها، وأعِد أول عدد مرشح لا يعثر عليه الفحص. وبحسب الحد، لن تختبر عددًا أكبر من n+1.
عندما تحتوي المصفوفة على الأعداد من 1 إلى n، يُعثر على كل عدد مرشح في المتوسط عند منتصف عملية الفحص، لذا فإن n = 10^4 يتطلب نحو n²/2 = 5 × 10^7 مقارنة.
الخوارزمية
- اجعل
candidateيساوي 1. - ابحث في
numsعن عنصر يساويcandidate، وتوقّف عند أول عنصر تجده. - إذا لم يطابق أي عنصر، فأعِد
candidate. - وإلا فأضف 1 إلى
candidateوابحث مرة أخرى. لن تتجاوز أبدًا n+1.
def firstMissingPositive(nums):
n = len(nums)
# n values cannot cover all of 1..n+1, so one of these candidates is missing
for candidate in range(1, n + 2):
found = False
for num in nums:
if num == candidate:
found = True
break
if not found:
return candidateعلِّم القيم من 1 إلى n في مصفوفة الأعلام
الفكرة
بما أن الإجابة لا تتجاوز n+1، فتجاهل أي قيمة أقل من 1 أو أكبر من n. تسجّل مصفوفة منطقية present بطول n+1 القيم المتبقية، لذا لا تُخزَّن قيمة مثل 10^9 أبدًا. أعد أول v من 1 إلى n تكون رايته false، أو n+1 إذا كانت جميع الرايات مضبوطة.
في المثال الأول n = 6: تُضبط الرايات للقيم 1 و2 و3 و5، ويتم تجاهل -2 و9، وأول راية غير مضبوطة هي 4. يوفّر المرور الخطي مرتين زمنًا قدره O(n)، وتستهلك الرايات ذاكرة قدرها O(n).
الخوارزمية
- أنشئ
present، وهي مجموعة من n+1 أعلام مضبوطة على false. - لكل قيمة
vفيnumsبحيث1 ≤ v ≤ n، اضبطpresent[v]على true. - أعِد أول
vمن 1 إلى n يكون علمه false. - إذا لم يوجد، فأعِد n+1.
def firstMissingPositive(nums):
n = len(nums)
# present[v] says whether v is in nums; only 1..n can matter
present = [False] * (n + 1)
for num in nums:
if 1 <= num <= n:
present[num] = True
for v in range(1, n + 1):
if not present[v]:
return v
return n + 1ضع كل قيمة في خانة منفصلة
الفكرة
تنتمي القيمة v إلى الفهرس v-1. عندما تكون كل قيمة من 1 إلى n في موضعها، فإن أول فهرس i لا يحتوي على i+1 يحدد الإجابة.
عند كل فهرس، بدّل القيمة إلى موضعها ما دامت بين 1 وn ولم يكن موضعها يحتوي عليها بالفعل. وقد تحتاج القيمة التي تعود إلى نقلها أيضًا. إن التحقق من موضع القيمة، لا من i، يمنع التكرارات: في [1, 1]، يجد الرقم 1 الثاني الرقم 1 في الفهرس 0، فيبقى مكانه.
في المثال الأول، يرسل الفهرس 0 القيمة 5 إلى موضعها، ثم القيمة 2 التي تعود؛ ولاحقًا، تنتقل القيمتان 1 و3 إلى موضعيهما، لتبقى المصفوفة [1, 2, 3, -2, 5, 9]: الفهرس 3 هو أول خانة غير صحيحة، لذا فالإجابة هي 4.
كل عملية تبديل تضع قيمة واحدة في موضعها نهائيًا، لذا تنفذ الحلقات الداخلية n عملية تبديل على الأكثر إجمالًا: زمن O(n)، وذاكرة O(1)، باستثناء R، التي تنسخ المتجه الذي تعدّله.
الخوارزمية
- لكل فهرس
iمن 0 إلى n-1: - ما دام
1 ≤ nums[i] ≤ nوnums[nums[i]-1] ≠ nums[i]، بدّلnums[i]معnums[nums[i]-1]. - بعد مرحلة الترتيب، اعثر على أول فهرس
iحيثnums[i] ≠ i+1وأعِدi+1. - إذا كانت كل خانة تحتوي على قيمتها الخاصة، فأعِد n+1.
def firstMissingPositive(nums):
n = len(nums)
for i in range(n):
# Keep swapping until slot i holds a value that has no slot or is already home
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
home = nums[i] - 1
nums[i], nums[home] = nums[home], nums[i]
# The first slot that does not hold its own value names the answer
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1
أخطاء شائعة وحالات حدّية
- إيقاف التبديلات عندما تكون
nums[i] == i+1بدلًا من إيقافها عندما يحتوي الموضع الصحيح بالفعل على القيمة. مع[1, 1]، ستُبدَّل قيمتا 1 إلى ما لا نهاية. - استخدام
ifبدلًا منwhileلإجراء التبديل. في المثال الأول، لا تصل القيمة 2 التي تعود من الفهرس 4 إلى الفهرس 1 أبدًا، وستُعيد 2 بدلًا من 4. - كتابة
nums[i] = nums[nums[i]-1]ثم استخدامnums[i]مجددًا للفهرسة، ما يقرأ فهرس الموضع الصحيح بعد تغيّره. احفظ فهرس الموضع الصحيح أولًا. - تخطّي التحقق من النطاق، ما يوجّه 0 أو -2 أو 10^9 إلى فهرس خارج المصفوفة.
- إرجاع n عندما يكون كل موضع صحيحًا. بالنسبة إلى
[4, 2, 1, 3]، الإجابة هي 5.
أسئلة شائعة3
ما هو التعقيد الزمني لمسألة العدد الموجب الأول المفقود؟
يعمل حلّ الترتيب في زمن O(n) وبمساحة إضافية O(1). تقع حلقة while داخل حلقة for، لكن كل عملية تبديل تضع قيمة في فهرسها النهائي، لذا لا يتجاوز مجموع عمليات التنفيذ n عملية تبديل. إصدار مصفوفة الأعلام يعمل في زمن O(n) وبذاكرة O(n)، أما المسح بحثًا عن كل قيمة مرشحة فيستغرق O(n²).
لماذا لا تكون الإجابة أبدًا أكبر من n+1؟
الأعداد من 1 إلى n+1 هي n+1 قيمة مختلفة، والمصفوفة ذات الطول n تحتوي على n قيم مختلفة كحد أقصى، لذا فإن إحداها مفقودة. تكون الإجابة n+1 بالضبط عندما تحتوي المصفوفة على كل قيمة من 1 إلى n.
هل يغيّر الحل الموضعي مصفوفة الإدخال؟
نعم، إنها تعيد ترتيب القيم. إذا كان المستدعِي يحتاج إلى الترتيب الأصلي، فانسخ المصفوفة أولًا، وهذا يعيد استهلاك الذاكرة الإضافي إلى O(n). وهناك طريقة أخرى تعمل في المكان، تستبدل كل قيمة خارج النطاق من 1 إلى n بـ n+1، ثم تعلّم على وجود v بجعل nums[v-1] سالبة؛ وهي تغيّر المصفوفة أيضًا.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def firstMissingPositive(nums):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
nums = [5, -2, 1, 3, 2, 9]
الإخراج المتوقع
4