Sort Colors
لديك مصفوفة nums تكون فيها كل قيمة إما 0 أو 1 أو 2. تخيّل أنها تمثّل ثلاثة ألوان، مثل الأحمر والأبيض والأزرق. أعد ترتيب المصفوفة بحيث تأتي كل الأصفار أولًا، ثم كل الآحاد، ثم كل الأثنين، وأعِدها.
حلّ المسألة دون استخدام دالة فرز من مكتبة. الفكرة هي الاستفادة مما تعرفه عن القيم.
الدالة
- numsinteger-array
- الألوان، كلٌّ منها 0 أو 1 أو 2
- تُرجعinteger-array
- القيم نفسها، مع كل الأصفار أولًا، ثم كل الآحاد، ثم كل الاثنينات
القيود
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]
- الشرح
- تحتوي المصفوفة على صفرين، وثلاثة آحاد، واثنين من الرقم 2، لذا تكون النتيجة كما هي تمامًا: صفران، ثم ثلاثة آحاد، ثم اثنان من الرقم 2.
- المدخلات
- nums = [2, 0, 2]
- المخرجات
- [0, 2, 2]
- الشرح
- لا يوجد أي رقم 1 على الإطلاق. ينتقل الرقم 0 الوحيد إلى المقدمة، ويتبعه الرقمان 2.
- المدخلات
- nums = [1]
- المخرجات
- [1]
- الشرح
- تكون القيمة المفردة مرتبة بالفعل، لذا تعود المصفوفة دون تغيير.
+17 اختبارات مخفية عند الإرسال
سؤال إضافي
ما الذي ستغيّره إذا كان هناك k لونًا بدلًا من ثلاثة، وكان k أصغر بكثير من طول المصفوفة؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
لا يمكن أن تظهر إلا ثلاث قيم مختلفة. ما الذي يتيح لك ذلك فعله ولا يتيحه الفرز العام؟
يتم عدّ القيم 0 و1 و2 وإعادة كتابة المصفوفة على مرحلتين. تخيّل في مرحلة واحدة ثلاث مناطق تنمو في الوقت نفسه: الأصفار في المقدمة، والاثنانات في المؤخرة، والواحدات بينهما.
احتفظ بثلاثة مؤشرات:
lowوmidوhigh. اقرأnums[mid]: إذا كانت 0، فبدّلها معlow، وإذا كانت 2، فبدّلها معhigh، أما إذا كانت 1 فتبقى. بعد التبديل معhigh، اقرأ الموضع نفسه مجددًا.
الحل
أي ترتيب يعطي الترتيب الصحيح، لذا فالسؤال الحقيقي هو ما الذي تتيح لك القيم الثلاث تخطيه. وبما أن القيمتين 0 و1 و2 فقط يمكن أن تظهر، يمكنك عدّها وإعادة كتابة المصفوفة على مرحلتين. وباستخدام ثلاثة مؤشرات تحدد أين تنتهي الأصفار وأين تبدأ الأعداد 2، يمكنك أيضًا وضع كل قيمة في مكانها في مرحلة واحدة. ويُعرف هذا التقسيم بمرحلة واحدة باسم خوارزمية العلم الوطني الهولندي.
الترتيب الفقاعي يدويًا
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
سيُنجز فرز المكتبة المهمة في زمن O(n log n)، لكن قواعد المسألة تستبعد ذلك، لأن المُحاوِر يريد أن يرى ما ستفعله مع حقيقة أن هناك ثلاث قيم فقط. لذا فإن الخيار الأساسي هو خوارزمية فرز تكتبها بنفسك، وأبسطها من حيث التنفيذ الصحيح هي فرز الفقاعات: مرّ على المصفوفة، وكلما كان عنصران متجاوران بترتيب غير صحيح، بدّل بينهما.
تدفع تمريرة واحدة أكبر قيمة تصادفها حتى النهاية، مثل فقاعة ترتفع. بعد التمريرة الأولى يستقر الموضع الأخير، وبعد الثانية يستقر الموضعان الأخيران، لذا فإن n-1 تمريرة تترك المصفوفة بأكملها مرتبة. في [2, 1, 0] تنقل التمريرة الأولى القيمة 2 إلى النهاية، فتصبح [1, 0, 2]، ثم تبدّل التمريرة الثانية بين 1 و0.
هذه الخوارزمية بطيئة لأن كل تمريرة تقارن كل زوج لم يستقر ترتيبه بعد: نحو n²/2 مقارنة إجمالًا. عندما تكون n = 1.5 × 10^4، فهذا يعني أكثر من 10^8 مقارنة، بالإضافة إلى تبديل لكل زوج يبدأ بترتيب غير صحيح، ولا يستفيد أيٌّ من هذا العمل من حقيقة وجود ثلاث قيم فقط.
الخوارزمية
- نفّذ 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عُدَّ كلَّ لون، ثم أَعِد الكتابة
الفكرة
يقضي الترتيب بالفقاعات كل وقته في مقارنة العناصر المتجاورة، لكنك تعرف بالفعل القيم الموجودة. إذا كانت المصفوفة تحتوي على قيمتين 0، وثلاث قيم 1، وقيمتين 2، فالإجابة محسومة قبل أن تحرّك أي شيء: قيمتان 0، وثلاث قيم 1، وقيمتان 2. المهم هو الأعداد فقط.
لذا اقرأ المصفوفة مرة واحدة واحسب عدد كل قيمة. ثم أعد الكتابة فيها بدءًا من البداية: count[0] أصفار، ثم count[1] آحاد، ثم count[2] اثنان. هذا هو الترتيب بالعد، وهو آمن هنا لأن القيم المتساوية قابلة للاستبدال. فالـ 1 هو 1، لذا لا حاجة إلى الحفاظ على أي شيء من الترتيب الأصلي.
وهذا يعني مرورين وثلاثة عدّادات، بزمن 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 وmid إلى الأمام. القيمة التي تعود من low هي 1 (أو 0 نفسه، إذا لم يُصادف أي 1 بعد)، لذا فهي في موضعها بالفعل. ينتمي العنصر 2 إلى الخلف: بدّله مع nums[high] وحرّك high إلى الخلف، لكن أبقِ mid في مكانه، لأن القيمة التي جاءت من high لم تُقرأ بعد.
في كل خطوة يتحرك mid إلى الأمام أو high إلى الخلف، لذا يفقد الجزء غير المقروء عنصرًا واحدًا في كل مرة، وتنتهي الحلقة بعد n خطوة. تتبّع [2, 0, 2]: يُبدّل العنصر 2 الأول مع العنصر 2 الأخير، وينخفض high إلى 1؛ وما زال الفهرس 0 يحتوي على 2، فيُبدّل مع 0 وينخفض high إلى 0؛ والآن يحتوي الفهرس 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عندما يكونhighفهرس آخر عنصر لم يُقرأ بعد. عندما يلتقيان، تظل تلك الخانة غير مقروءة. في[1, 0]تتوقف الحلقة قبل أن تقرأ 0، وتُرجع[1, 0]. - السماح لـ
highبالانخفاض إلى ما دون الصفر باستخدام فهرس غير موقّع. مصفوفة تحتوي على 2 فقط، مثل[2]، تجعل قيمةhighتصل إلى -1. في Rust، حيث تكون الفهارس من النوعusize، أبقِhighعند خانة واحدة بعد الجزء الذي لم يُقرأ بعد، كما يفعل كود Rust. - افتراض ظهور كل لون. لا يحتوي
[2, 0, 2]على 1، وقد تحتوي المصفوفة على لون واحد فقط. تتعامل قواعد المؤشرات مع الحالتين دون حالات خاصة، لذا لا تضف أيًا منها.
أسئلة شائعة4
ما هي مسألة العلم الوطني الهولندي؟
طرح إدسخر ديكسترا المسألة: إذا كانت هناك أجسام من ثلاثة ألوان في صف واحد، وهي الأحمر والأبيض والأزرق لألوان العلم الهولندي، فاجمع كل لون معًا في مرور واحد، باستخدام عمليات التبديل فقط. مسألة فرز الألوان هي المسألة نفسها باستخدام الأرقام 0 و1 و2. حلّه هو التقسيم باستخدام ثلاثة مؤشرات: low وmid وhigh.
ما هو التعقيد الزمني وتعقيد المساحة لخوارزمية Sort Colors؟
يعمل الحل ذو المرور الواحد بزمن O(n)، لأن كل خطوة تُقلّص الجزء غير المقروء بمقدار خلية واحدة. ويستخدم مساحة إضافية مقدارها O(1): ثلاثة فهارس وقيمة مؤقتة للتبديل. ويحقق فرز العد الحدود نفسها، لكنه يقرأ المصفوفة مرتين.
لماذا لا يتحرك mid بعد تبديله مع high؟
القيمة التي تعود من high لم تُقرأ من قبل، لذا قد تكون 0 أو 1 أو 2. إن تجاوز mid لها سيترك 0 أو 2 في المنتصف. أما التبديل مع low فهو مختلف: فكل ما بين low وmid يساوي 1، لذا تكون القيمة التي تعود معروفة ويمكن لـmid أن يتقدم.
هل يُعدّ الترتيب بالعدّ إجابة مقبولة لمسألة فرز الألوان؟
يحقق حدودًا زمنية قدرها O(n) وحدودًا مكانية قدرها O(1)، ويقبله كثير من المحاورين بوصفه إجابة أولى. توقّع سؤالًا لاحقًا يطلب المرور مرة واحدة، وهو التقسيم باستخدام ثلاثة مؤشرات. يُعدّ العدّ أداة أفضل عندما يكون هناك ألوان كثيرة، لأن التقسيم يفصل العناصر إلى ثلاث مجموعات فقط.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def sortColors(nums):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
nums = [2, 1, 0, 2, 0, 1, 1]
المتوقع
[0, 0, 1, 1, 1, 2, 2]