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]
- הסבר
- המערך מכיל שני אפסים, שלוש אחדות ושני 2, ולכן התוצאה היא בדיוק כך: שני אפסים, אחר כך שלוש אחדות, ואז שני 2.
- קלט
- nums = [2, 0, 2]
- פלט
- [0, 2, 2]
- הסבר
- אין בכלל 1. ה־0 היחיד עובר לקדמת הרשימה, ושני ה־2 באים אחריו.
- קלט
- nums = [1]
- פלט
- [1]
- הסבר
- ערך יחיד כבר מסודר, לכן המערך חוזר ללא שינוי.
+17 בדיקות נסתרות בשליחה
שאלת המשך
מה היית משנה אילו היו k צבעים במקום שלושה, כאשר k קטן בהרבה מאורך המערך?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
יכולים להופיע רק שלושה ערכים שונים. מה זה מאפשר לך לעשות שמיון כללי לא יכול?
ספירת ה־0, ה־1 וה־2 וכתיבה מחדש של המערך מתבצעות בשני מעברים. במעבר אחד, דמיינו שלושה אזורים שגדלים בו־זמנית: 0 בחזית, 2 מאחור ו־1 באמצע.
שמרו שלושה אינדקסים:
low,midו-high. קראו אתnums[mid]: אם הערך הוא 0, החליפו עםlow; אם הוא 2, החליפו עםhigh; אם הוא 1, השאירו אותו במקומו. אחרי החלפה עםhigh, קראו שוב את אותו מיקום.
פתרון
כל מיון נותן את הסדר הנכון, ולכן השאלה האמיתית היא על מה שלושת הערכים מאפשרים לך לדלג. מכיוון שיכולים להופיע רק 0, 1 ו־2, אפשר לספור אותם ולכתוב מחדש את המערך בשני מעברים. בעזרת שלושה מצביעים שמסמנים היכן מסתיימים ה־0 והיכן מתחילים ה־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ספרו כל צבע, ואז כתבו מחדש
האינטואיציה
מיון בועות מקדיש את כל זמנו להשוואה בין איברים שכנים, אבל את הערכים שקיימים כבר ידועים לך. אם המערך מכיל שני אפסים, שלוש אחדות ושני זוגות, התשובה קבועה עוד לפני שמזיזים משהו: שני אפסים, שלוש אחדות ושני זוגות. רק הכמויות חשובות.
לכן עוברים על המערך פעם אחת וסופרים כל ערך. אחר כך כותבים עליו מחדש מההתחלה: 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
מהי בעיית הדגל הלאומי ההולנדי?
אדסחר דייקסטרה הציג את הבעיה כך: בהינתן עצמים בשלושה צבעים בשורה — אדום, לבן וכחול, צבעי דגל הולנד — יש לקבץ כל צבע יחד במעבר אחד, תוך שימוש בהחלפות בלבד. Sort Colors היא אותה בעיה עם המספרים 0, 1 ו־2. הפתרון שלו הוא חלוקה באמצעות שלושה מצביעים: low, mid ו־high.
מהי סיבוכיות הזמן והמרחב של מיון צבעים?
הפתרון במעבר אחד פועל בזמן 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]