Sort Colors
لديك مصفوفة nums تحتوي كل قيمة فيها على 0 أو 1 أو 2: ثلاثة ألوان، مثل الأحمر والأبيض والأزرق. أعد ترتيب المصفوفة بحيث تأتي جميع الأصفار أولًا، ثم جميع الواحدات، ثم جميع الاثنينات، وأعِدها. حلّ المسألة دون استخدام دالة فرز من مكتبة.
الدالة
- numsinteger-array
- الألوان، كلٌّ منها 0 أو 1 أو 2
- تُرجعinteger-array
- القيم نفسها، مع كل 0 أولًا، ثم كل 1، ثم كل 2
القيود
1 ≤ nums.length ≤ 1.5 × 104- كل عنصر من
nums[i]هو0أو1أو2. - قد يكون لونٌ مفقودًا، وقد تحتوي المصفوفة على لون واحد.
أمثلة
- المدخلات
- nums = [2, 1, 0, 2, 0, 1, 1]
- المخرجات
- [0, 0, 1, 1, 1, 2, 2]
- الشرح
- تحتوي المصفوفة على قيمتين 0، وثلاث قيم 1، وقيمتين 2، لذا فالنتيجة هي بالضبط: قيمتان 0، ثم ثلاث قيم 1، ثم قيمتان 2.
- المدخلات
- nums = [2, 0, 2]
- المخرجات
- [0, 2, 2]
- الشرح
- لا يوجد أي 1 على الإطلاق. ينتقل الصفر الوحيد إلى المقدمة، ويتبعه الرقمان 2.
- المدخلات
- nums = [1]
- المخرجات
- [1]
- الشرح
- تكون القيمة المفردة مرتبة بالفعل، لذا تعود المصفوفة دون تغيير.
سؤال إضافي
ما الذي ستغيّره إذا كان هناك k ألوان بدلًا من ثلاثة، وكان k أصغر بكثير من طول المصفوفة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
لا يمكن أن تظهر سوى ثلاث قيم مختلفة. ما الذي يتيح لك ذلك فعله ولا يتيحه الفرز العام؟
يتم عدّ الأصفار والآحاد والاثنينات وإعادة كتابة المصفوفة على مرحلتين. في المرحلة الأولى، تخيّل ثلاث مناطق تنمو في الوقت نفسه: الأصفار في المقدمة، والاثنينات في النهاية، والآحاد بينهما.
احتفِظ بثلاثة مؤشرات:
lowوmidوhigh. اقرأnums[mid]: إذا كانت القيمة 0، فبدّلها معlow، وإذا كانت 2، فبدّلها معhigh، أما إذا كانت 1 فتبقى كما هي. بعد التبديل معhigh، اقرأ الموضع نفسه مرة أخرى.
الحل
لا يمكن أن تظهر سوى القيم 0 و1 و2، لذا يمكنك عدّها وإعادة كتابة المصفوفة في تمريرين. ويمكن استخدام ثلاثة مؤشرات تحدد نهاية قيم 0 وبداية قيم 2 لإنجاز ذلك في تمرير واحد، مع وضع كل قيمة في مكانها أثناء قراءتها. ويُسمّى هذا التقسيم خوارزمية العلم الوطني الهولندي.
الترتيب الفقاعي يدويًا
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
من دون استخدام دالة ترتيب من مكتبة، يكون خط الأساس خوارزمية ترتيب تكتبها بنفسك. يمرّ ترتيب الفقاعات على المصفوفة ويبدّل أي عنصرين متجاورين إذا لم يكونا بالترتيب الصحيح. تنقل كلّ دورة أكبر قيمة تصادفها إلى النهاية، لذا بعد n-1 دورة يصبح كل موضع نهائيًا.
يجري نحو n²/2 مقارنة: أكثر من 10^8 عندما يكون n = 1.5 × 10^4، ولا تستفيد أيٌّ منها من حقيقة أن القيم الموجودة هي ثلاث فقط.
الخوارزمية
- نفّذ n-1 تمريرة على المصفوفة.
- في كل تمريرة، قارن كل زوج من العناصر المتجاورة
nums[j]وnums[j + 1]التي لم تستقر في مواضعها النهائية بعد، وبدّل بينهما عندما يكون العنصر الأيسر أكبر. - بعد التمريرة ذات الرقم
done(بدءًا من 0)، تحتل المواضعdone + 1الأخيرة قيمها النهائية، لذا تتوقف التمريرة التالية قبلها. - أعِد
nums.
def sortColors(nums):
n = len(nums)
for done in range(n - 1):
# One pass: the largest value left so far bubbles to index n-1-done.
for j in range(n - 1 - done):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return numsعُدَّ كلَّ لون، ثم أَعِد الكتابة
الفكرة
القيم المتساوية قابلة للتبادل، لذا فإن الأعداد وحدها هي المهمة. في المثال الأول، يحدد وجود صفرين وثلاثة آحاد واثنين من الرقم 2 الإجابة قبل أن تحرّك أي شيء.
اقرأ المصفوفة مرة واحدة لعدّ كل قيمة، ثم أعد الكتابة فيها بدءًا من البداية: count[0] من الأصفار، وcount[1] من الآحاد، وcount[2] من الرقم 2. تُسمى هذه الطريقة بفرز العدّ. تمريرتان وثلاثة عدّادات تعطيان زمنًا قدره O(n) ومساحة قدرها O(1).
الخوارزمية
- أنشئ ثلاثة عدّادات، جميعها تساوي 0.
- اقرأ كل قيمة وأضف واحدًا إلى عدّادها.
- اكتب
count[0]من الأصفار بدءًا من البداية، ثمcount[1]من الآحاد، ثمcount[2]من الاثنتين. - أعِد
nums.
def sortColors(nums):
count = [0, 0, 0] # how many 0s, 1s and 2s
for x in nums:
count[x] += 1
i = 0
for color in range(3):
for _ in range(count[color]):
nums[i] = color
i += 1
return numsتمريرة واحدة باستخدام ثلاثة مؤشرات (العلم الوطني الهولندي)
الفكرة
نمِّ ثلاث مناطق أثناء القراءة. كل ما يقع قبل low هو 0، وكل ما يبدأ من low وحتى ما قبل mid هو 1، وكل ما يقع بعد high هو 2، أما nums[mid] إلى nums[high] فلم يُقرأ بعد.
اقرأ nums[mid]. تكون القيمة 1 في منطقتها بالفعل، لذا حرّك mid إلى الأمام. تتبادل القيمة 0 موضعها مع nums[low] ويتحرك المؤشران إلى الأمام: فالقيمة التي تعود من low هي 1، أو 0 نفسها إذا لم تُرصد أي قيمة 1 بعد، لذا تكون في موضعها الصحيح. تتبادل القيمة 2 موضعها مع nums[high] ويتراجع high، لكن يبقى mid في مكانه، لأن القيمة التي جاءت من high لم تُقرأ بعد.
في كل خطوة يتقدم mid أو يتراجع high، لذا تنتهي الحلقة بعد n خطوات. في [2, 0, 2] تتبادل القيمة 2 الأولى موضعها مع الأخيرة ويتراجع high إلى 1؛ وما يزال الفهرس 0 يحتوي على 2، فتتبادل موضعها مع 0؛ ثم تبقى 0 في مكانها، فتصبح النتيجة [0, 2, 2].
الخوارزمية
- عيّن
low = 0وmid = 0وhighإلى الفهرس الأخير. - ما دام
mid ≤ high، فاقرأnums[mid]. - إذا كانت القيمة 0، فبدّلها مع
nums[low]وحرّكlowوmidخطوة واحدة إلى اليمين. - إذا كانت القيمة 1، فحرّك
midخطوة واحدة إلى اليمين. - إذا كانت القيمة 2، فبدّلها مع
nums[high]وحرّكhighخطوة واحدة إلى اليسار. اتركmidفي مكانه. - أعِد
nums.
def sortColors(nums):
# nums[:low] are 0s, nums[low:mid] are 1s, nums[high + 1:] are 2s.
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
# The value swapped in from high is unread, so mid stays.
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return nums
أخطاء شائعة وحالات حدّية
- تحريك
midإلى الأمام بعد التبديل معhigh. القيمة التي تصل لم تُقرأ بعد: في[1, 2, 0]يتم تبديل 2 مع 0، وتجاوز 0 يعيد[1, 0, 2]. - التكرار ما دام
mid < high. عندما يلتقيان، تظل تلك الخانة غير مقروءة: في[1, 0]تتوقف الحلقة قبل قراءة 0 وتعيد[1, 0]. - السماح لـ
highبأن يصبح أقل من الصفر باستخدام فهرس غير موقّع. مصفوفة تحتوي على قيم 2 فقط، مثل[2]، تجعلhighيصل إلى -1، وهذا يؤدي إلى تجاوز سعةusizeفي Rust. أبقِhighعند موضع واحد بعد الجزء غير المقروء.
أسئلة شائعة3
ما هي مشكلة العلم الوطني الهولندي؟
طرح إدسخر ديكسترا المسألة: رتّب أجسامًا من ثلاثة ألوان في صف، الأحمر والأبيض والأزرق، ألوان العلم الهولندي، بحيث يكون كل لون متجمعًا، في مرور واحد باستخدام عمليات التبديل فقط. مسألة فرز الألوان هي المسألة نفسها باستخدام 0 و1 و2، وحلّه هو التقسيم باستخدام ثلاثة مؤشرات.
ما التعقيد الزمني وتعقيد المساحة لخوارزمية Sort Colors؟
يعمل الحل ذو المرور الواحد في زمن O(n)، لأن كل خطوة تقلّص الجزء غير المقروء بمقدار خلية واحدة. ويستخدم مساحة إضافية مقدارها O(1): ثلاثة فهارس وقيمة مؤقتة للتبديل. ويحقق الترتيب بالعد الحدود نفسها، لكنه يقرأ المصفوفة مرتين.
هل يُعدّ الترتيب بالعدّ إجابةً مقبولة لمسألة Sort Colors؟
يلتزم بحدود زمنية قدرها O(n) وحدود مكانية قدرها O(1)، ويقبله كثير من المحاورين كإجابة أولى. توقّع أن يُطلب منك بعد ذلك المرور على العناصر مرة واحدة. يُعدّ العدّ أداة أفضل عندما يكون هناك ألوان كثيرة، لأن التقسيم لا يفصل إلا بين ثلاث مجموعات.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def sortColors(nums):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
nums = [2, 1, 0, 2, 0, 1, 1]
الإخراج المتوقع
[0, 0, 1, 1, 1, 2, 2]