Leaders in an Array
ניתן לך מערך של מספרים שלמים nums. איבר הוא מנהיג אם הוא גדול או שווה לכל איבר שמימינו. לאיבר האחרון אין איברים מימינו, ולכן הוא תמיד מנהיג. החזר את כל המנהיגים, לפי הסדר שבו הם מופיעים ב-nums משמאל לימין.
פונקציה
- numsinteger-array
- מערך המספרים השלמים שיש לחפש בו
- מחזירהinteger-array
- המובילים של nums, משמאל לימין
אילוצים
1 ≤ nums.length ≤ 25000-109 ≤ nums[i] ≤ 109
דוגמאות
- קלט
- nums = [12, 5, 9, 3, 6, 2]
- פלט
- [12, 9, 6, 2]
- הסבר
- 2 נמצא אחרון, ולכן הוא מוביל. 6 מנצח את 2 שאחריו, 9 מנצח את 3, את 6 ואת 2, ו־12 מנצח את כולם. 5 מפסיד ל־9 ו־3 מפסיד ל־6, ולכן התשובה היא
[12, 9, 6, 2].
- קלט
- nums = [4, 7, 7, 1, 7]
- פלט
- [7, 7, 7]
- הסבר
- סופרים גם שוויונות: ל־7 במיקומים 1 ו־2 יש רק 7 שווה מימינם, ולכן שניהם מובילים יחד עם ה־7 האחרון. אחרי 4 ואחרי 1 יש 7.
- קלט
- nums = [-3]
- פלט
- [-3]
- הסבר
- איבר יחיד הוא האחרון, ולכן הוא מוביל, שלילי או לא.
שאלת המשך
אם הערכים מגיעים בזה אחר זה, ואחרי כל ערך עליך לדווח על המובילים עד כה, איך מעדכנים את הרשימה בזמן O(1) בממוצע לכל ערך?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
כדי להחליט אם
nums[i]הוא מוביל, צריך רק מספר אחד על החלק שמימינו. איזה מספר?איבר הוא מוביל בדיוק כאשר הוא גדול או שווה למקסימום של כל מה שנמצא מימינו. אם תעבור מהקצה הימני, תוכל לעדכן את המקסימום תוך כדי התקדמות.
מתחילים מהאיבר האחרון, והוא משמש גם כמוביל הראשון שנמצא וגם כמקסימום הנוכחי. נעים שמאלה: כל ערך שגדול או שווה למקסימום הנוכחי הוא מוביל והופך למקסימום החדש. אוספים את המובילים מימין לשמאל, ולכן הופכים את הסדר שלהם לפני שמחזירים אותם.
פתרון
קרא משמאל, כל איבר דורש סריקה חדשה של הסיומת שלו. עבור מימין במקום זאת: הדבר היחיד שצריך לדעת על הסיומת הוא הערך הגדול ביותר שלה, ומשתנה אחד מספיק כדי לשמור אותו. כך בדיקה של O(n²) הופכת למעבר יחיד.
בדקו את כל מה שמימין
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
יישם את ההגדרה: עבור כל אינדקס i, סרוק את האיברים שאחריו ועצור באיבר הראשון שגדול ממש מ־nums[i]. אם הסריקה מגיעה לסוף, nums[i] מוביל. בודקים את האינדקסים משמאל לימין, ולכן המובילים מתקבלים לפי הסדר. ב־[12, 5, 9, 3, 6, 2], הסריקה של 5 נעצרת ב־9 ושל 3 נעצרת ב־6.
העלות נובעת מהסריקות שמגיעות עד הסוף. כאשר יש 24,999 ערכים שווים ולאחריהם ערך אחד גדול יותר, כל איבר עובר כמעט על כל המערך: בערך 25,000 × 25,000 / 2, כלומר יותר מ־3 × 10^8 השוואות.
אלגוריתם
- צרו רשימת תוצאות ריקה.
- עבור כל אינדקס
i, סרקו אתjמ־i + 1ועד הסוף. - אם אחד מהערכים
nums[j]גדול מ־nums[i], עצרו:nums[i]אינו מוביל. - אם לא קיים
jכזה, הוסיפו אתnums[i]לתוצאה. - החזירו את התוצאה.
def leaders(nums):
n = len(nums)
result = []
for i in range(n):
is_leader = True
for j in range(i + 1, n):
if nums[j] > nums[i]: # a bigger value on the right rules it out
is_leader = False
break
if is_leader:
result.append(nums[i])
return resultמעבר אחד מימין עם ערך מקסימלי מתעדכן
האינטואיציה
להיות גדול לפחות כמו כל איבר שמימין לו זהה להיות גדול לפחות כמו הערך המרבי שלהם. כשמתקדמים מימין לשמאל, אפשר לעדכן את הערך המרבי הזה. האיבר האחרון מוביל וקובע את הערך המרבי. כל איבר שמשמאלו מוביל אם הוא גדול לפחות כמו הערך המרבי, ואז הוא הופך לערך המרבי החדש; אחרת, יש מימינו ערך גדול יותר.
ב־[12, 5, 9, 3, 6, 2]: 2 מוביל, אחריו 6, אחריו 9, ואז 12, ואילו 3 ו־5 נמוכים מהערך המרבי. מצאת את [2, 6, 9, 12]; בהיפוך הסדר, זו התשובה.
כל איבר מושווה פעם אחת: זמן O(n) ו־O(1) מקום נוסף מלבד התוצאה. גרסת R מסמנת את האיברים המובילים בווקטור logical(n), ולכן המקום הנוסף שלה הוא O(n).
אלגוריתם
- שים את האיבר האחרון בתוצאה והגדר את
bestלערכו. - התקדם עם
iמהאינדקס הלפני אחרון עד 0. - אם
nums[i] ≥ best, הוסף אתnums[i]לתוצאה והגדר אתbestלערכו. - הפוך את התוצאה כך שהאיברים המובילים יופיעו משמאל לימין, והחזר אותה.
def leaders(nums):
n = len(nums)
best = nums[n - 1] # the largest value to the right of the current index
found = [best] # the last element is always a leader
for i in range(n - 2, -1, -1):
if nums[i] >= best:
best = nums[i]
found.append(nums[i])
found.reverse() # collected right to left, returned left to right
return found
מלכודות ומקרי קצה
- שימוש ב־
>במקום ב־≥בהשוואה למקסימום הנוכחי. במערך[4, 7, 7, 1, 7]כל 7 הוא מוביל, אבל השוואה מחמירה משאירה רק את האחרון. - התחלת המקסימום ב־0 במקום באיבר האחרון.
[-1, -5]חייב להחזיר את שניהם, אבל מקסימום של 0 פוסל אותם. - החזרת המובילים בסדר שבו מצאת אותם,
[2, 6, 9, 12]במקום[12, 9, 6, 2]. - הוספת האיבר האחרון פעמיים על ידי התחלת הלולאה באינדקס האחרון לאחר שכבר הוספת אותו לתוצאה.
- השוואת כל איבר רק לשכן שלו. ב־
[5, 3, 9], המספר 5 גדול מ־3 שלצדו, אבל 9 גורם לכך שהתשובה היא[9].
שאלות נפוצות3
מהי סיבוכיות הזמן של מציאת מנהיגים במערך?
O(n) במעבר יחיד מימין, משום שכל איבר מושווה פעם אחת למקסימום המצטבר. בדיקת כל איבר מול כל האיברים שמימינו עולה O(n²) במקרה הגרוע, למשל כשכל הערכים שווים.
האם האיבר האחרון תמיד מוביל?
כן. איבר מוביל חייב להיות גדול לפחות כמו כל איבר שמימינו, ולאיבר האחרון אין איברים כאלה, לכן התנאי מתקיים ואין מה לבדוק.
האם ערכים שווים נחשבים למובילים?
כאן, כן: איבר מוביל חייב להיות גדול או שווה לכל איבר שמימינו, ולכן ב־[4, 7, 7, 1, 7] כל שלושת איברי ה־7 מובילים. בגרסאות מסוימות נדרש להיות גדול ממש; במקרה כזה משווים באמצעות >, ורק האחרון מבין הערכים השווים מוביל.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def leaders(nums):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
nums = [12, 5, 9, 3, 6, 2]
הפלט הצפוי
[12, 9, 6, 2]