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