Missing Number
لديك قائمة nums تضم n أعداد صحيحة متميزة، يقع كل منها بين 0 وn. يحتوي النطاق من 0 إلى n على n+1 عددًا، لذا فإن عددًا واحدًا منها فقط غير موجود في القائمة. أعد هذا العدد المفقود.
الدالة
- numsinteger-array
- عدد صحيح متميز من بين الأعداد من 0 إلى n، بأي ترتيب
- تُرجعinteger
- العدد الوحيد من 0 إلى n غير الموجود في nums
القيود
n == nums.length1 ≤ n ≤ 1040 ≤ nums[i] ≤ n- جميع القيم في
numsمتميزة.
أمثلة
- المدخلات
- nums = [4, 2, 0, 1]
- المخرجات
- 3
- الشرح
- تحتوي القائمة على 4 قيم، لذا فإن النطاق من 0 إلى 4. وهي تحتوي على 0 و1 و2 و4، والعدد 3 هو العدد الوحيد الذي لا يوجد له تطابق.
- المدخلات
- nums = [1]
- المخرجات
- 0
- الشرح
- عند وجود قيمة واحدة، يكون النطاق بين 0 و1. تحتوي القائمة على 1، لذا فإن 0 مفقود.
- المدخلات
- nums = [0, 1, 2]
- المخرجات
- 3
- الشرح
- كل عدد أقل من 3 موجود، لذا فالعدد المفقود هو 3 نفسه، أي الحد الأعلى للنطاق. وهو ليس فهرسًا في القائمة، ولهذا يتطلب الحد الأعلى الانتباه.
سؤال إضافي
إذا كانت القائمة مرتبة، فهل يمكنك العثور على الرقم المفقود في زمن O(log n) باستخدام البحث الثنائي؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
أنت تعرف بالضبط الأعداد التي يجب أن تحتوي عليها القائمة: كل عدد صحيح من
0إلىn. هل يوجد عدد واحد يمكنك حسابه لهذا النطاق الكامل ومقارنته بالعدد نفسه المحسوب للقائمة؟مجموع الأعداد الصحيحة من
0إلىnيساويn(n+1)/2، ومجموع القائمة أقل بمقدار القيمة المفقودة بالضبط. تعمل عملية XOR بالطريقة نفسها دون أي خطر من تجاوز السعة، لأن XOR قيمة مع نفسها يساوي0.مرّ على القائمة مرة واحدة مع تطبيق XOR تراكمي. ابدأه عند
n، وعند كل فهرسiطبّق XOR على كلٍّ منiوnums[i]. كل عدد يظهر مرتين يُلغي الآخر، ويبقى العدد المفقود.
الحل
أنت تعرف بالضبط ما يجب أن تحتويه القائمة: كل عدد صحيح من 0 إلى n. البحث عن كل عدد منها على حدة ينجح، لكنه يكرر مسحًا كاملًا لكل عدد. بدلًا من ذلك، لخّص النطاق الكامل والقائمة كلًّا في قيمة واحدة، وهي المجموع أو XOR، والفرق بينهما هو العدد المفقود. يتطلب ذلك مرورًا واحدًا ولا يحتاج إلى ذاكرة إضافية.
تحقّق من كل مرشّح
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
الإجابة هي أحد الأعداد الـn+1 من 0 إلى n. خذها بالترتيب وافحص القائمة بحثًا عن كل عدد منها. أول عدد مرشّح لا تطابقه أي قيمة هو العدد المفقود.
هذا صحيح لأن كل عدد في النطاق إما موجود في القائمة أو هو الإجابة، ولأن القائمة لا تحتوي على أعداد مكررة، فلا بد أن يفشل البحث عن مرشح واحد بالضبط.
هذه الطريقة بطيئة لأن كل عدد مرشّح يتطلب فحصًا لما يصل إلى n قيمة. عندما تكون الفجوة قرب الطرف الأعلى، يُبحث عن كل الأعداد المرشّحة تقريبًا: عند n = 10^4 ووجود الفجوة قرب النهاية، يكون عدد المقارنات نحو 5 × 10^7. ومضاعفة حجم القائمة تجعل العمل أكبر بأربعة أضعاف.
الخوارزمية
- كرّر
candidateمن0حتىn، شاملًا. - ابحث في
numsعن قيمة تساويcandidate. - إذا عثر البحث عليها، فانتقل إلى المرشح التالي.
- إذا انتهى البحث دون تطابق، فأعِد
candidate.
def missingNumber(nums):
n = len(nums)
for candidate in range(n + 1):
# "in" on a list scans it from the start: O(n) per candidate.
if candidate not in nums:
return candidate
return -1اطرح المجموع من المجموع المتوقع
الفكرة
إذا لم يكن هناك أي عدد مفقود، لاحتوت القائمة على كل عدد من 0 إلى n، ومجموع هذه الأعداد هو n(n+1)/2. القائمة الفعلية هي هذه المجموعة الكاملة بعد حذف عدد واحد منها، لذا يقل مجموعها عن المجموع الكامل بمقدار ذلك العدد بالضبط.
في [4, 2, 0, 1]، تكون قيمة n هي 4، ومجموع النطاق الكامل هو 4 × 5 / 2 = 10. مجموع القائمة هو 7، والفرق بين 10 و7 هو 3.
تجمع القائمة في مرور واحد، لذا يكون الزمن O(n)، وتحتفظ بمجموع جارٍ واحد. هنا لا يتجاوز المجموع الكامل تقريبًا 5 × 10^7، وهذا يناسب عددًا صحيحًا من 32 بت. أما عندما تكون قيمة n أكبر بكثير، فتتجاوز الصيغة سعة عدد صحيح من 32 بت، لذلك تُجري إصدارات Java وC وC++ وC# وRust العمليات الحسابية باستخدام 64 بت.
الخوارزمية
- لتكن
nطولnums. - احسب المجموع الكامل
n(n+1)/2. - اجمع كل قيمة في
nums. - أعِد المجموع الكامل مطروحًا منه مجموع القائمة.
def missingNumber(nums):
n = len(nums)
expected = n * (n + 1) // 2
return expected - sum(nums)أجرِ عملية XOR بين الفهارس والقيم
الفكرة
تلغي عملية XOR الأزواج. a ^ a تساوي 0، وa ^ 0 تساوي a، ولا يهم ترتيب العمليات. لذا، إذا أجريت XOR على مجموعة من الأعداد يظهر فيها كل عدد مرتين باستثناء قيمة واحدة، فستُلغى الأزواج وتبقى تلك القيمة.
أنشئ مثل هذه المجموعة انطلاقًا من المسألة: الفهارس من 0 إلى n، بالإضافة إلى القيم في nums. يظهر العدد الموجود في القائمة مرةً كفهرس ومرةً كقيمة، لذا يُلغى. أما العدد المفقود فيظهر كفهرس فقط، لذا يبقى. تمر الحلقة على الفهارس من 0 إلى n-1، لذا ابدأ النتيجة من n لتضمين الفهرس الأخير.
بالنسبة إلى [4, 2, 0, 1]: ابدأ بـ 4، ثم أجرِ XOR على 0 و4، و1 و2، و2 و0، و3 و1. تُلغى جميع قيم 4 و2 و1 و0، ويبقى 3. هذه عملية مرور واحدة بقيمة واحدة متراكمة، وعلى عكس الجمع، لا تكبر هذه القيمة أبدًا لتتجاوز البتات التي يستخدمها n أصلًا، لذا لا يمكن أن يحدث تجاوز للسعة.
الخوارزمية
- عيّن
resultإلىn، طولnums. - لكل فهرس
i، نفّذ XOR بينresultوiوnums[i]. - أعِد
result.
def missingNumber(nums):
# Start with n, the one index the loop below never reaches.
result = len(nums)
for i, value in enumerate(nums):
result ^= i ^ value
return result
أخطاء شائعة وحالات حدّية
تأتي معظم الإجابات الخاطئة من طرفَي النطاق.
- نسيان أن
nنفسه قد يكون مفقودًا. في[0, 1, 2]الإجابة هي 3، وهذا ليس فهرسًا في القائمة. يجب أن يبدأ إصدار XOR منn، كما يجب أن يعيد المسح المرتّب الذي يبحث عن أولnums[i] != iالقيمةnعندما تتطابق جميع المواضع. - استخدام حجم نطاق غير صحيح. تتراوح الأعداد من
0إلىn، أيn+1عددًا، لذا فإن المجموع الكامل هوn(n+1)/2، وليس(n-1)n/2. - افتراض أن
0موجود دائمًا. في[1]الإجابة هي 0، والشيفرة التي تبدأ البحث من 1 ستفوّتها. - حدوث تجاوز للسعة في إصدار المجموع. في الحساب ذي 32 بت، يتجاوز حاصل الضرب
n(n+1)السعة عندما يتجاوزnنحو 46,000، قبل أن تساعد القسمة على 2، كما أنn(n+1)/2نفسه يتوقف عن الملاءمة قرب 65,000. استخدم حسابًا ذي 64 بت، أو XOR.
أسئلة شائعة3
ما هو التعقيد الزمني لمسألة العدد المفقود؟
يعمل حلّا الجمع وXOR في زمن O(n) وبمساحة إضافية O(1)، لأنهما يقرآن كل قيمة مرة واحدة ويحتفظان برقم واحد. أما البحث في القائمة عن كل قيمة مرشحة فيستغرق O(n²). والفرز أولًا ثم البحث عن الفجوة يستغرق O(n log n).
لماذا يعثر XOR على الرقم المفقود؟
تؤدي عملية XOR لعدد مع نفسه إلى 0، وعملية XOR مع 0 لا تغيّر شيئًا، كما أن الترتيب لا يهم. عند إجراء XOR لجميع الفهارس من 0 إلى n مع جميع القيم، يظهر كل عدد موجود في القائمة مرتين ويلغي نفسه. أما العدد المفقود فيظهر مرة واحدة فقط بوصفه فهرسًا، لذا فهو النتيجة.
هل ينبغي أن تستخدم صيغة الجمع أم XOR؟
كلاهما يحتاج إلى مرور واحد وذاكرة ثابتة. يسهل شرح المجموع، لكن في الحساب ذي 32 بت، تفيض قيمة حاصل الضرب n(n+1) بمجرد أن يتجاوز n نحو 46,000، لذا تحتاج إلى حساب ذي 64 بت. لا يحدث فيضان في XOR أبدًا. في Python وRuby واللغات الأخرى ذات الأعداد الصحيحة غير المحدودة، يختفي الفرق.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def missingNumber(nums):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
nums = [4, 2, 0, 1]
الإخراج المتوقع
3