Find Minimum in Rotated Sorted Array
רשימה של מספרים שלמים שונים ממוינת בסדר עולה ואז עברה סיבוב: מספר כלשהו של איברים, אולי אפס, נלקחו מההתחלה והועברו לסוף באותו סדר. לדוגמה, סיבוב של [2, 5, 9, 11, 13, 15, 17] ב־3 מקומות יוצר את [11, 13, 15, 17, 2, 5, 9]. נתונה לך הרשימה המסובבת nums. החזר את הערך הקטן ביותר בה בזמן O(log n).
פונקציה
- numsinteger-array
- הרשימה הממוינת המסובבת של מספרים שלמים שונים
- מחזירהinteger
- הערך הקטן ביותר ב־nums
אילוצים
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 104- כל הערכים ב־
numsשונים זה מזה. numsהיא רשימה עולה שסובבה ב־kכלשהו, כאשר0 ≤ k < nums.length;k = 0משאיר אותה ללא סיבוב.
דוגמאות
- קלט
- nums = [11, 13, 15, 17, 2, 5, 9]
- פלט
- 2
- הסבר
- הערכים עולים מ־11 ל־17 ואז יורדים ל־2, שבו מתחילה הריצה השנייה. החיפוש רואה ש־17 > 9 באינדקס 3, ולכן המינימום נמצא מימינו; ואז 5 ≤ 9 ו־2 ≤ 5 מזיזים את
hiבחזרה עד שהטווח מצטמצם לאינדקס 4 בלבד, שבו נמצא 2.
- קלט
- nums = [4, 7, 10, 12]
- פלט
- 4
- הסבר
- הרשימה הזו סובבה ב־0, ולכן היא עדיין ממוינת והערך המינימלי הוא הערך הראשון שלה. כל ערך אמצעי קטן או שווה לערך האחרון, ולכן
hiממשיך לנוע שמאלה עד שהוא מגיע לאינדקס 0, שמכיל את 4.
- קלט
- nums = [30, -6, 0, 8, 19]
- פלט
- -6
- הסבר
- ארבעה ערכים הועברו מההתחלה לסוף, כך שהערך הגדול ביותר, 30, מופיע כעת ראשון והערך הקטן ביותר, -6, נמצא באינדקס 1. החיפוש מצמצם את הטווח לאינדקסים 0 ו-1, רואה ש-30 > -6, ומעביר את
loל-1.
+17 בדיקות נסתרות בשליחה
שאלת המשך
האם אפשר להחזיר את הערך ה־k הקטן ביותר של nums בזמן O(log n), בלי למיין אותו?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
ברשימה ממוינת כל ערך גדול מהערך שלפניו. הסיבוב מפר את הסדר הזה במקום אחד בלבד. היכן נמצא הערך הקטן ביותר ביחס למקום הזה?
השווה את הערך האמצעי לערך האחרון בטווח שלך. אם הערך האמצעי גדול יותר, הערכים חייבים לרדת איפשהו אחריו. אם הוא קטן יותר, הקטע מהאמצע ועד הסוף עולה בלי לרדת כלל.
השאר את
loואתhiסביב הערך המינימלי. כאשרnums[mid] > nums[hi], העבר אתloאלmid + 1; אחרת העבר אתhiאלmid, מכיוון שייתכן ש-midעצמו הוא הערך המינימלי. עצור כאשרloשווה ל-hi.
פתרון
רשימה ממוינת שעברה סיבוב מורכבת משני מקטעים עולים, [11, 13, 15, 17] ואז [2, 5, 9]. הערך המינימלי הוא הערך הראשון במקטע השני, ממש אחרי המקום היחיד שבו הערכים יורדים. מעבר על הרשימה מוצא את הירידה הזאת ב־O(n). השוואת ערך אמצעי אחד לערך האחרון בטווח מגלה באיזה צד של הירידה נמצא האמצע, ולכן חיפוש בינארי מוצא אותו ב־O(log n).
הולכים עד שהערכים יורדים
האינטואיציה
ברשימה ממוינת, כל ערך גדול מהערך שקדם לו. סיבוב הרשימה משאיר את שני הרצפים ממוינים ויוצר בדיוק מקום אחד שבו הסדר הזה מופר: הערך הגדול ביותר ואחריו הערך הקטן ביותר. לכן יש לעבור משמאל לימין ולהחזיר את הערך הראשון שקטן מהשכן שמשמאלו. אם אין ערך כזה, הרשימה סובבה ב־0 והמינימום הוא nums[0].
ב־[11, 13, 15, 17, 2, 5, 9] המעבר מגיע ל־13, ל־15 ול־17, שכל אחד מהם גדול מהערך שלפניו, ונעצר באינדקס 4, שבו 2 קטן מ־17. זה כבר עדיף על מציאת המינימום של כל הערכים, כי המעבר נעצר בנקודת הירידה, אבל נקודת הירידה יכולה להיות בכל מקום. כשהסיבוב הזיז איבר אחד, כמו ב־[2, 3, 4, 5, 6, 7, 8, 1], המעבר קורא את הרשימה כולה: 5000 השוואות עבור 5000 איברים, בעוד שחיפוש בינארי דורש 13.
אלגוריתם
- עבור כל אינדקס
iמ-1 עדn-1, השווה ביןnums[i]לביןnums[i-1]. - אם
nums[i] < nums[i-1], החזר אתnums[i]: הרצף השני מתחיל שם. - אם הלולאה מסתיימת, הרשימה לא עברה סיבוב: החזר את
nums[0].
def findMin(nums):
for i in range(1, len(nums)):
if nums[i] < nums[i - 1]:
return nums[i] # the only drop: the second run starts here
return nums[0] # no drop: the list was not rotatedחיפוש בינארי מול הערך האחרון
האינטואיציה
שמרו על הבטחה אחת: הערך המינימלי נמצא בין lo ל־hi, כולל. בתחילת הדרך הטווח הוא הרשימה כולה. בדקו את הערך האמצעי והשוו אותו ל־nums[hi], הערך האחרון בטווח.
אם nums[mid] > nums[hi], הערכים יורדים במקום כלשהו בין mid ל־hi, והערך המינימלי הוא הערך שמיד אחרי הירידה הזאת, כלומר מימין ל־mid: קבעו lo = mid + 1. אחרת nums[mid] < nums[hi] (הערכים שונים זה מזה), ולכן nums[mid..hi] עולה ואין בו ירידה. הערך המינימלי הוא אז nums[mid] או ערך כלשהו לפניו, ולכן קבעו hi = mid. אל תעברו את mid: ייתכן שהוא הערך המינימלי. כל אחת מההזזות שומרת על ההבטחה ומצמצמת את הטווח, וכאשר lo מגיע ל־hi, הערך היחיד שנותר הוא הערך המינימלי.
עקבו אחר הדוגמה הראשונה, [11, 13, 15, 17, 2, 5, 9]. לטווח 0 עד 6 יש אמצע 3, והערך בו הוא 17, גדול מ־nums[6] = 9, ולכן lo הופך ל־4. לטווח 4 עד 6 יש אמצע 5, והערך בו הוא 5, שאינו גדול מ־9, ולכן hi הופך ל־5. לטווח 4 עד 5 יש אמצע 4, והערך בו הוא 2, שאינו גדול מ־5, ולכן hi הופך ל־4. החזירו nums[4] = 2.
בכל צעד הטווח נחצה, ולכן הלולאה רצה לכל היותר בערך log2(n) פעמים: 13 צעדים עבור 5000 איברים, תוך שימוש בזיכרון נוסף לשני אינדקסים.
אלגוריתם
- הגדר
lo = 0ואתhi = n-1. - כל עוד
lo < hi, חשב אתmid = lo + (hi - lo) / 2. - אם
nums[mid] > nums[hi], הגדרlo = mid + 1. - אחרת, הגדר
hi = mid. - כשהלולאה מסתיימת, החזר את
nums[lo].
def findMin(nums):
lo, hi = 0, len(nums) - 1 # the minimum sits in nums[lo..hi]
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the values drop after mid, so the minimum is right of it
else:
hi = mid # nums[mid..hi] climbs: the minimum is at mid or left of it
return nums[lo]
מלכודות ומקרי קצה
הלולאה אורכת ארבע שורות, ולכל שורה יש גרסה שגויה מפתה.
- כתיבת
hi = mid - 1בענף השני. הענף הזה מתבצע כשייתכן ש-midעצמו הוא המינימום. ב-[3, 1, 2]הערך האמצעי 1 אינו גדול מ-2, ולכןhiיורד ל-0 והפונקציה מחזירה 3. - הרצה של הלולאה כל עוד
lo ≤ hi. ברגע ש-loשווה ל-hi,midשווה לשניהם,nums[mid] > nums[hi]הוא false, והשינוי שלhi = midאינו משנה דבר: הלולאה לעולם אינה מסתיימת. יש לעצור כשהטווח מכיל איבר אחד, באמצעותlo < hi. - השוואה מול
nums[lo]במקום מולnums[hi]. ברשימה שלא סובבה[1, 2, 3, 4, 5], הערך האמצעי 3 גדול מ-nums[0] = 1, ונראה שהירידה נמצאת מימין, ולכן החיפוש מתרחק מהמינימום האמיתי באינדקס 0 ומחזיר 4. - החזרת
loבמקוםnums[lo]. המשימה מבקשת את הערך; האינדקס הוא התשובה לשאלה אחרת (ראו את השאלות הנפוצות על מספר הסיבובים). - הנחה שהרשימה סובבה. סיבוב ב-0 מותר, וקוד שמחפש ירידה בלי מנגנון חלופי קורא מעבר לסוף או לא מחזיר דבר. יש להחזיר את
nums[0]כשאין ירידה.
שאלות נפוצות4
מהי סיבוכיות הזמן של מציאת הערך המינימלי במערך ממוין שעבר סיבוב?
זמן O(log n) ומקום נוסף O(1) באמצעות חיפוש בינארי. בכל צעד נשארים עם חצי אחד של הטווח, ולכן רשימה של 5000 איברים דורשת לכל היותר 13 השוואות. הסריקה לאיתור הירידה היא O(n): היא קוראת כל איבר כשהערך המינימלי נמצא בסוף.
למה להשוות את nums[mid] ל־nums[hi] ולא ל־nums[lo]?
כי nums[hi] תמיד קובע באיזה צד נמצא הערך המינימלי, ואילו nums[lo] לא. אם nums[mid] > nums[hi], הערכים חייבים להימצא בין mid ל־hi; אחרת nums[mid..hi] עולה והערך המינימלי נמצא ב־mid או לפניו. עם nums[lo], התוצאה nums[mid] > nums[lo] מתאימה גם לרשימה שלא סובבה, שבה הערך המינימלי הוא nums[lo], וגם לרשימה שסובבה, שבה הוא נמצא מימין ל־mid.
איך מוצאים כמה פעמים סובבו מערך ממוין?
בצע את אותו חיפוש בינארי והחזר את lo, האינדקס של הערך המינימלי, במקום את nums[lo]. אם סופרים סיבוב כהעברת האיבר האחרון לתחילת המערך, האינדקס הזה הוא מספר הסיבובים. אם סופרים אותו כהעברת האיבר הראשון לסוף, כפי שעושה הבעיה הזו, מספר הסיבובים הוא (n - lo) mod n: ב־[11, 13, 15, 17, 2, 5, 9] הערך המינימלי נמצא באינדקס 4, ו־7 פחות 4 נותן את 3 הערכים שהועברו.
האם החיפוש הבינארי עובד כשהמערך מכיל כפילויות?
לא נותר ללא שינוי. ב־[2, 2, 2, 0, 2], ייתכן ש־nums[mid] יהיה שווה ל־nums[hi], ואז אי אפשר לשלול אף אחד מהצדדים. צמצום הטווח באמצעות hi = hi - 1 במקרה כזה בטוח, כי עותק של nums[hi] נשאר בטווח ב־mid, אבל רשימה של ערכים שווים שבתוכה מוסתר ערך קטן אחד עולה O(n).
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def findMin(nums):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
nums = [11, 13, 15, 17, 2, 5, 9]
צפוי
2