Second Largest Number
ניתנת לך רשימה של מספרים שלמים nums. החזר את הערך השני בגודלו מבין הערכים הייחודיים: הערך הגדול ביותר שקטן ממש מהמקסימום. ערכים יכולים לחזור על עצמם, ולכן עבור [5, 5, 3] התשובה היא 3, ולא 5. הרשימה תמיד מכילה לפחות שני ערכים שונים.
פונקציה
- numsinteger-array
- רשימת המספרים השלמים, עם לפחות שני ערכים שונים
- מחזירהinteger
- הערך הגדול ביותר שקטן מהערך המרבי
אילוצים
2 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109numsמכיל לפחות שני ערכים שונים.
דוגמאות
- קלט
- nums = [4, 9, 2, 7, 9]
- פלט
- 7
- הסבר
- הערך המרבי הוא
9. הוא מופיע פעמיים, אבל עותק שני של הערך המרבי לא נחשב, ולכן התשובה היא הערך הבא אחריו,7.
- קלט
- nums = [-5, -1, -8]
- פלט
- -5
- הסבר
- מהגדול לקטן, הערכים הם
-1,-5,-8. הערך השני בגודלו הוא-5, אף שהוא שלילי.
- קלט
- nums = [6, 6, 6, 3]
- פלט
- 3
- הסבר
- קיימים רק שני ערכים שונים,
6ו־3. לא משנה כמה פעמים6חוזר, הערך השני בגודלו הוא3.
שאלת המשך
האם תוכל להחזיר במעבר אחד את הערך השלישי בגודלו, ללא כפילויות, באמצעות שלושה משתנים וללא מיון?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
כדי למצוא את הערך המרבי צריך משתנה אחד. מה משתנה שני יאפשר לך לזכור כשאתה קורא את הרשימה?
עקוב אחר הערך הגדול ביותר ואחר הערך השני בגודלו, השונים זה מזה. ערך חדש יכול להיות גדול מהערך הגדול ביותר, להימצא ממש בין השניים, או לא לשנות דבר.
אתחל את שני המשתנים שלהלן לכל ערך מותר. אם
x > largest, העבר אתlargestאלsecondושמור אתx. אחרת, אםxנמצא ביניהם באופן ממש, שמור אותו ב־second.
פתרון
שני פרטים הופכים את זה לקשה יותר ממציאת הערך המרבי. הערך המרבי יכול להופיע כמה פעמים, ואין לדווח על הופעה חוזרת כעל הערך השני בגודלו. התשובה יכולה להיות שלילית, ולכן משתנה שמתחיל ב־0 יוביל לתשובה שגויה ברשימה שכולה שלילית. מעקב אחר שני הערכים השונים הגדולים ביותר במעבר אחד, באמצעות השוואות מחמירות, מטפל בשני המקרים.
מיון וירידה מעבר למקסימום
האינטואיציה
מיינו עותק מהקטן לגדול. הערך המרבי נמצא בסוף, וייתכן שיופיע שם כמה פעמים ברצף. עברו שמאלה מהסוף, דלגו על כל ההעתקים של הערך המרבי; הערך הראשון ששונה ממנו הוא השני בגודלו. עבור [6, 6, 6, 3] העותק הממויין הוא [3, 6, 6, 6]: מדלגים על שלושה 6 ומגיעים אל 3.
החזרת האיבר שלפני האחרון היא הטעות הקלאסית כאן. עבור [4, 9, 2, 7, 9] היא מחזירה 9, שוב את הערך המרבי. אי אפשר להתקדם מעבר לתחילת הרשימה, כי הרשימה מכילה לפחות שני ערכים שונים.
התשובה נכונה, אבל מיון מסדר את כל הערכים, כשמעניין אותך רק שני הערכים הגדולים ביותר. העלות היא זמן של O(n log n) וזיכרון של O(n) עבור העותק.
אלגוריתם
- העתיקו את
numsומיינו את העותק מהקטן לגדול. - התחילו את האינדקס
iבמיקום האחרון. - כל עוד הערך ב-
iשווה לערך המרבי, הזיזו אתiצעד אחד שמאלה. - החזירו את הערך שב-
i.
def secondLargest(nums):
ordered = sorted(nums)
i = len(ordered) - 1
# Step left past every copy of the maximum.
while ordered[i] == ordered[-1]:
i -= 1
return ordered[i]שתי מעברים
האינטואיציה
חלקו את המשימה לשני מעברים. המעבר הראשון מוצא את הערך המרבי, כמו ב־Find the Largest Number. המעבר השני מחפש את הערך הגדול ביותר שקטן ממש מהערך המרבי הזה. עבור [4, 9, 2, 7, 9] המעבר הראשון מוצא את 9, והמעבר השני מדלג על שתי ההופעות של 9 ושומר את הגדול ביותר מבין 4, 2 ו־7, שהוא 7.
אתחלו את second לערך קטן מכל ערך שהרשימה יכולה להכיל, למשל למספר השלם הקטן ביותר בשפה שלכם. ברשימה יש לפחות שני ערכים שונים, לכן יש ערך כלשהו שקטן מהערך המרבי, והוא תמיד יחליף את ערך האתחול הזה.
כל מעבר מוצא ערך מרבי מצטבר, ולכן הסיבוכיות הכוללת היא O(n) זמן ו־O(1) מקום. המחיר הוא קריאת הרשימה פעמיים, דבר שאינו אפשרי כשהערכים מגיעים בזה אחר זה ונעלמים אחרי שקוראים אותם.
אלגוריתם
- עבור בלולאה על
numsפעם אחת ושמור את הערך המקסימלי ב-largest. - הגדר את
secondלערך קטן מכל ערך מותר. - עבור בלולאה שוב. עבור כל
xשעבורוx < largestוגםx > second, הגדר אתsecondל-x. - החזר את
second.
def secondLargest(nums):
largest = nums[0]
for x in nums:
if x > largest:
largest = x
second = float("-inf") # below every allowed value
for x in nums:
if x < largest and x > second:
second = x
return secondמעבר אחד למעקב אחר שני הערכים הגבוהים ביותר
האינטואיציה
שמרו שני משתנים, largest ו-second, עבור שני הערכים השונים הגדולים ביותר שנראו עד כה. כל ערך חדש x נכנס לאחד משלושה מקרים. אם x גדול מ-largest, הערך הישן של largest יורד למקום השני ו-x תופס את המקום הראשון. אם x נמצא ממש בין second ל-largest, הוא הופך ל-second החדש. בכל מקרה אחר לא חל שינוי.
ההשוואות המחמירות הן שמטפלות בערכים כפולים. עבור [4, 9, 2, 7, 9]: largest הופך ל-4, ואז ל-9, כאשר second = 4. הערך 2 לא משנה דבר, 7 נמצא בין 4 ל-9, ולכן second = 7, והערך האחרון 9 שווה ל-largest, ולכן מדלגים עליו. התשובה היא 7.
אתחלו את שני המשתנים לערכים הנמוכים מכל ערך אפשרי. אתחול שניהם ל-0 מחזיר 0 עבור [-5, -1, -8], כי אף ערך לא גובר על 0. מכיוון שהרשימה מכילה שני ערכים שונים, second תמיד יסתיים בערך ממשי מתוך הרשימה.
אלגוריתם
- הגדר את
largestואתsecondלערכים נמוכים מכל ערך מותר. - עבור בלולאה על כל ערך
xב-nums. - אם
x > largest, העבר אתlargestאלsecondוהגדר אתlargestל-x. - אחרת, אם
x < largestוגםx > second, הגדר אתsecondל-x. - לאחר הלולאה, החזר את
second.
def secondLargest(nums):
# Both start below every allowed value.
largest = second = float("-inf")
for x in nums:
if x > largest:
second = largest # the old maximum drops to second place
largest = x
elif largest > x > second:
second = x
return second
מלכודות ומקרי קצה
רוב התשובות השגויות נובעות מכפילויות של הערך המרבי או מערכים שליליים.
- החזרת האיבר הלפני אחרון ברשימה הממוינת. כשיש ערך מרבי שחוזר על עצמו, כמו ב־
[4, 9, 2, 7, 9], זה שוב הערך המרבי. - אתחול המשתנים ל־
0. ב־[-5, -1, -8]אף ערך לא גדול מ־0, ולכן מוחזר0, מספר שאינו מופיע ברשימה. - כתיבת
x >= largestבמקרה הראשון.9שני מעביר את ה־9הראשון אלsecond, ומוחזר9. - עדכון
secondרק כשמופיע ערך מרבי חדש. ב־[10, 20, 15], ה־15אף פעם לא מגיע אלsecond, ומוחזר10. - הסרת כפילויות באמצעות set ואז מיון. זה עובד, אבל צורך זיכרון של
O(n)וזמן שלO(n log n)עבור פעולה שמעבר יחיד מספיק לה.
שאלות נפוצות3
איך מוצאים את המספר השני בגודלו במערך במעבר אחד?
שמור את הערכים הגדולים ביותר והשניים בגודלם, השונים זה מזה, שנראו עד כה. כשערך גדול מהערך הגדול ביותר, הערך הגדול ביותר הישן עובר למקום השני. כשערך נמצא строго בין השניים, הוא מחליף את הערך השני. לאחר מעבר אחד, המשתנה השני מכיל את התשובה.
מהי סיבוכיות הזמן של מציאת האיבר השני בגודלו?
שיטות המעבר האחד ושני המעברים דורשות שתיהן זמן O(n) ושטח נוסף של O(1). מיון תחילה דורש זמן O(n log n). אי אפשר להשיג זמן טוב יותר מ־O(n), כי יש לקרוא כל ערך לפחות פעם אחת.
איך כפילויות משפיעות על האיבר השני בגודלו?
בבעיה זו מבקשים את הערך השני בגודלו מבין הערכים השונים, ולכן מדלגים על עותקים של הערך המרבי. עבור [9, 9, 7], התשובה היא 7. בגרסאות מסוימות של השאלה סופרים במקום זאת מיקומים, והתשובה תהיה 9, לכן בדקו למה מתכוונים לפני שאתם כותבים קוד.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def secondLargest(nums):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
nums = [4, 9, 2, 7, 9]
הפלט הצפוי
7