Move Zeroes

Q: كيف تنقل الأصفار إلى النهاية دون تغيير ترتيب العناصر الأخرى؟

احتفظ بمؤشر write للموقع الفارغ التالي في المقدمة، وامسح باستخدام مؤشر ثانٍ. تُبدَّل كل قيمة غير صفرية تعثر عليها إلى موضع write ، ثم يتحرك write خطوة واحدة إلى اليمين. توضع القيم بالترتيب الذي تعثر عليها به، لذا لا يتغير ترتيبها النسبي أبدًا.

Q: هل يمكن تنفيذ نقل الأصفار بعدد أقل من عمليات الكتابة؟

نعم. بدلًا من التبديل، انسخ كل قيمة غير صفرية إلى nums[write] ، وبعد المسح املأ كل موضع من write حتى النهاية بالرقم 0. بهذه الطريقة، تتم الكتابة في كل موضع مرة واحدة على الأكثر. ويمكنك أيضًا تخطي التبديل عندما تكون قيمة read مساوية لقيمة write ، لأنه سيعيد قيمة إلى الموضع الذي توجد فيه بالفعل.

سهلمؤشران

+10

لديك مصفوفة من الأعداد الصحيحة nums. انقل كل 0 إلى نهاية المصفوفة، مع الحفاظ على ترتيب القيم الأخرى كما كان. أعد المصفوفة بعد إعادة ترتيبها، والتي لها الطول نفسه الذي لـ nums.

الدالة

moveZeroes(nums: integer-array) → integer-array

numsinteger-array: مصفوفة الأعداد الصحيحة المطلوب إعادة ترتيبها
تُرجعinteger-array: الأعداد ذات القيم غير الصفرية أولًا، بترتيبها الأصلي، وجميع الأصفار في النهاية

القيود

1 ≤ nums.length ≤ 5000
-10⁵ ≤ nums[i] ≤ 10⁵

أمثلة

المدخلات: nums = [0, 4, 0, 7, 2]
المخرجات: [4, 7, 2, 0, 0]
الشرح: القيم التي لا تساوي 0 هي 4 و7 و2، وتظل بهذا الترتيب في المقدمة. ويشغل الرقمان 0 المكانين الأخيرين.

+14 اختبارات مخفية عند الإرسال

سؤال إضافي

هل يمكنك نقل كل 0 إلى المقدمة بدلًا من ذلك، مع الحفاظ على ترتيب القيم الأخرى، في مرور واحد وباستخدام ذاكرة إضافية O(1)؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

ليس وضع الأصفار في النهاية هو الجزء الصعب. بل الصعب هو إبقاء القيم الأخرى بترتيبها الأصلي، وهذا يستبعد تبديل كل 0 بالعنصر الأخير. قسّم المصفوفة إلى منطقة أمامية تحتوي على القيم غير الصفرية التي عُثر عليها حتى الآن، وبقية العناصر. يقرأ أحد المؤشرين كل عنصر، ويحدد مؤشر ثانٍ الموضع الذي تنتمي إليه القيمة غير الصفرية التالية، وتُنجز عملية مرور واحدة المهمة في مكانها.

انسخ القيم غير الصفرية

الفكرة

أنشئ مصفوفة جديدة. مرّ على nums وانسخ كل قيمة ليست 0، بالترتيب الذي تصادفها فيه. ثم أضف أصفارًا حتى يصبح طول المصفوفة الجديدة مساويًا لطول nums. عدد الأصفار التي تضيفها هو عدد القيم التي تخطّيتها.

بالنسبة إلى [0, 4, 0, 7, 2]، تعطي خطوة النسخ [4, 7, 2]، ويجعلها صفران [4, 7, 2, 0, 0]. الترتيب صحيح لأنك تنسخ القيم بالترتيب الذي تقرؤها به.

تُقرأ كلّ قيمة مرة واحدة وتُكتب مرة واحدة، لذا يكون الزمن O(n). تستهلك المصفوفة الثانية ذاكرة O(n)، وهو ما يتجنبه النهج التالي.

الخوارزمية

أنشئ مصفوفة نتائج فارغة.
لكل قيمة في nums، أضِفها إلى مصفوفة النتائج إذا لم تكن 0.
أضِف أصفارًا حتى يصبح عدد عناصر مصفوفة النتائج مساويًا لعدد عناصر nums.
أعِد مصفوفة النتائج.

def moveZeroes(nums):
    result = [x for x in nums if x != 0]
    result += [0] * (len(nums) - len(result))
    return result

مؤشران، والتبديل في المكان

الفكرة

استخدم فهرسين. يمرّ read على كل عنصر من اليسار إلى اليمين. ويحدد write موضع القيمة التالية غير الصفرية. بعد كل خطوة، تصح حقيقتان: كل ما يقع قبل write هو القيم غير الصفرية التي صادفناها حتى الآن، بترتيبها الأصلي، وكل ما يقع من write حتى read هو 0.

عندما لا تكون nums[read] مساوية لـ 0، بدّلها مع nums[write] وحرّك write خطوة واحدة إلى اليمين. القيمة التي تصل إلى read هي 0 من منطقة الأصفار، أو القيمة نفسها عندما يتساوى الفهرسان. لا تقفز القيم غير الصفرية إلا فوق الأصفار، ولا تتجاوز بعضها بعضًا، لذلك يبقى ترتيبها محفوظًا.

في [0, 4, 0, 7, 2]: يتبادل الرقم 4 عند الفهرس 1 موضعه مع الفهرس 0، فنحصل على [4, 0, 0, 7, 2]. ويتبادل الرقم 7 عند الفهرس 3 موضعه مع الفهرس 1، فنحصل على [4, 7, 0, 0, 2]. ويتبادل الرقم 2 عند الفهرس 4 موضعه مع الفهرس 2، فنحصل على [4, 7, 2, 0, 0]. مرور واحد ومن دون مصفوفة ثانية: زمن O(n) وذاكرة O(1).

الخوارزمية

اضبط write على 0.
حرّك read من الفهرس الأول إلى الأخير.
إذا لم تكن قيمة nums[read] تساوي 0، فبدّل nums[read] مع nums[write]، ثم أضف 1 إلى write.
أعِد nums.

def moveZeroes(nums):
    write = 0  # nums[:write] holds the non-zero values found so far, in order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

أخطاء شائعة وحالات حدّية

عادةً ما تؤدي الأخطاء إما إلى تغيير ترتيب القيم الأخرى أو تخطي عناصر.

استبدال كل 0 بالعنصر الأخير ينقل الأصفار لكنه يخلط ترتيب البقية: تتحول [0, 4, 7] إلى [7, 4, 0].
حذف الأصفار من المصفوفة أثناء مرور فهرس عليها يؤدي إلى تخطي عناصر. في [0, 0, 5]، يؤدي حذف الفهرس 0 إلى انتقال الصفر الثاني إلى الفهرس 0 بينما تنتقل الحلقة إلى الفهرس 1. كما أن كل عملية حذف تُزيح بقية المصفوفة، ما يجعل الحلقة ذات تعقيد O(n²).
اختبر x != 0، وليس x > 0. القيم السالبة ليست أصفارًا: يجب أن تصبح [-1, 0, -2] على الصورة [-1, -2, 0]، لكن استخدام x > 0 يجعل نسخة النسخ تُرجع [0, 0, 0].
يجب أن تعود المصفوفة التي لا تحتوي على أصفار، أو التي تحتوي على أصفار فقط، كما هي دون تغيير. في نسخة التبديل، يظل read وwrite متساويين حتى أول 0، لذا لا تُغيّر عمليات التبديل هذه شيئًا.
في Lua وR، تبدأ المصفوفات من 1، لذا يبدأ write من 1 أيضًا.

أسئلة شائعة4

ما هو التعقيد الزمني لنقل الأصفار؟

O(n). تقرأ الطريقتان كل عنصر مرة واحدة. يتطلب نسخ القيم غير الصفرية إلى مصفوفة جديدة ذاكرة إضافية بمقدار O(n)، بينما تعمل طريقة تبديل المؤشرين داخل المصفوفة بذاكرة إضافية بمقدار O(1).

كيف تنقل الأصفار إلى النهاية دون تغيير ترتيب العناصر الأخرى؟

احتفظ بمؤشر write للموقع الفارغ التالي في المقدمة، وامسح باستخدام مؤشر ثانٍ. تُبدَّل كل قيمة غير صفرية تعثر عليها إلى موضع write، ثم يتحرك write خطوة واحدة إلى اليمين. توضع القيم بالترتيب الذي تعثر عليها به، لذا لا يتغير ترتيبها النسبي أبدًا.

هل يمكن تنفيذ نقل الأصفار بعدد أقل من عمليات الكتابة؟

نعم. بدلًا من التبديل، انسخ كل قيمة غير صفرية إلى nums[write]، وبعد المسح املأ كل موضع من write حتى النهاية بالرقم 0. بهذه الطريقة، تتم الكتابة في كل موضع مرة واحدة على الأكثر. ويمكنك أيضًا تخطي التبديل عندما تكون قيمة read مساوية لقيمة write، لأنه سيعيد قيمة إلى الموضع الذي توجد فيه بالفعل.

لماذا تُعدّ مسألة نقل الأصفار مسألةَ مؤشّرين؟

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

Python

def moveZeroes(nums):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

nums = [0, 4, 0, 7, 2]

المتوقع

[4, 7, 2, 0, 0]