Find the Largest Number
ניתנת לך רשימה לא ריקה של מספרים שלמים nums. החזר את הערך הגדול ביותר בה. הערכים יכולים להיות שליליים, ולכן גם התשובה יכולה להיות שלילית. מצא אותו באמצעות השוואות משלך, ללא פונקציית מקסימום מובנית כמו max.
פונקציה
- numsinteger-array
- רשימת המספרים השלמים לחיפוש
- מחזירהinteger
- הערך הגדול ביותר ב־nums
אילוצים
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
דוגמאות
- קלט
- nums = [3, 17, 4, 12, 9]
- פלט
- 17
- הסבר
- בקריאה משמאל, הערך הגדול ביותר עד כה הוא
3, ואז17. אף אחד מהערכים4,12או9אינו גדול מ-17, לכן התשובה היא17.
- קלט
- nums = [-8, -3, -11, -3]
- פלט
- -3
- הסבר
- כל הערכים שליליים, ו־
-3הוא הקרוב ביותר לאפס, ולכן הוא הגדול ביותר. הוא מופיע פעמיים, אבל מחזירים את הערך, לא את המיקום שלו.
- קלט
- nums = [42]
- פלט
- 42
- הסבר
- ברשימה עם ערך אחד, הערך הזה הוא הגדול ביותר.
שאלת המשך
האם תוכל להחזיר גם את הערך הגדול ביותר וגם את הערך הקטן ביותר באמצעות כ־3n/2 השוואות במקום 2n, על ידי השוואת הערכים בזוגות תחילה?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
קרא את הערכים בזה אחר זה. מהו הדבר היחיד שעליך לזכור לגבי הערכים שכבר ראית?
זכור רק את הערך הגדול ביותר עד כה. כל ערך חדש או עולה עליו או לא.
התחילו את הערך המרבי הנוכחי ב־
nums[0], ולא ב־0, מכיוון שכל הערכים עשויים להיות שליליים. השוו אותו לכל ערך והשאירו את הגדול יותר.
פתרון
כל ערך שעליו מדלגים עלול להיות הגדול ביותר, ולכן כל פתרון קורא כל איבר לפחות פעם אחת. ההחלטה האמיתית היחידה היא היכן להתחיל את המקסימום המצטבר. מתחילים אותו באיבר הראשון, לעולם לא ב־0, כי כל הערכים ברשימה עשויים להיות שליליים.
מיון של עותק ולקיחת הערך האחרון
האינטואיציה
ברשימה ממוינת מהקטן לגדול, הערך הגדול ביותר נמצא בסוף. העתק את nums כדי שהרשימה של מי שקרא לפונקציה תישאר כפי שהייתה, מיין את העותק והחזר את האיבר האחרון שלו. עבור [3, 17, 4, 12, 9] העותק הממוין הוא [3, 4, 9, 12, 17], והאיבר האחרון הוא 17.
התשובה נכונה, אבל המיון עושה הרבה יותר ממה שנחוץ לך. הוא מסדר את כל הערכים, פעולה שדורשת בערך n log n השוואות — בערך 60,000 עבור n = 5000 — כשאתה רוצה למצוא רק את הגדול ביותר. גם העתקת הרשימה צורכת זיכרון בנפח O(n).
ב-JavaScript וב-TypeScript, העבר פונקציית השוואה ל-sort. בלי פונקציה כזאת, הוא משווה את המספרים כטקסט, ולכן 12 ו-17 מופיעים לפני 3.
אלגוריתם
- העתק את
nums. - מיין את העותק מהקטן לגדול, תוך השוואת המספרים כמספרים.
- החזר את האיבר האחרון בעותק הממויין.
def findMax(nums):
ordered = sorted(nums) # a sorted copy, smallest first
return ordered[-1]מעבר אחד עם ערך מקסימלי מצטבר
האינטואיציה
שומרים משתנה אחד, largest, עבור הערך הגדול ביותר שנראה עד כה. מתחילים אותו ב-nums[0], משווים אותו לכל ערך ומחליפים אותו בכל פעם שערך גדול ממנו. כשהלולאה מסתיימת, largest הושווה לכל איבר, ולכן אין שום ערך ברשימה שגדול ממנו.
עבור [3, 17, 4, 12, 9], הערך של largest מתחיל ב-3, הופך ל-17 ונשאר 17 במהלך הבדיקה של 4, 12 ו-9. אלה n-1 השוואות מועילות ומשתנה נוסף אחד.
התחלה ב-nums[0] היא מה שמאפשר לרשימות של מספרים שליליים לעבוד. אם מתחילים ב-0 במקום זאת, [-8, -3, -11, -3] אף פעם לא מכילה ערך שגדול ממנו, ולכן מחזירים 0, ערך שאפילו לא נמצא ברשימה.
אלגוריתם
- הגדר את
largestל־nums[0]. - עבור על כל ערך
xב־nums. - אם
x > largest, הגדר אתlargestל־x. - לאחר הלולאה, החזר את
largest.
def findMax(nums):
largest = nums[0] # never 0: every value may be negative
for x in nums:
if x > largest:
largest = x
return largest
מלכודות ומקרי קצה
הלולאה קצרה, ולכן הטעויות הן במקום שבו היא מתחילה ובמה שהיא קוראת.
- התחלה של
largestב־0או ב־-1. כל רשימה שכל הערכים בה קטנים מערך ההתחלה הזה תחזיר מספר שאינו נמצא ברשימה. - התחלה במספר קטן מומצא, כמו
-1000000. הערכים כאן מגיעים עד-10^9, ולכן ערך ההתחלה עדיין יהיה הגדול ביותר. אין צורך לנחש:nums[0]. - קריאה של
nums[0]ב־Lua או ב־R, שבהן האיבר הראשון הואnums[1]. Lua מחזירהnilו־R מחזירה וקטור ריק. - שימוש בלולאה עם
i ≤ nבשפה שבה האינדקסים מתחילים ב־0, מה שקורא איבר אחד מעבר לסוף. - מיון ללא משווה מספרי ב־JavaScript או ב־TypeScript. סדר הטקסט של
[3, 17, 4, 12, 9]מסתיים ב־9, ולכן מוחזר9במקום17.
שאלות נפוצות3
מהי סיבוכיות הזמן של מציאת הערך המרבי במערך?
מעבר אחד נמשך O(n) זמן וצורך O(1) מקום נוסף. שום שיטה על מערך לא ממוין לא יכולה לעשות טוב יותר, כי כל איבר שלא קראת עשוי להיות הגדול ביותר. מיון מראש עולה O(n log n), וזה איטי יותר בלי שום תועלת.
איך מוצאים את המספר הגדול ביותר במערך בלי להשתמש ב־max?
שמרו את האיבר הראשון במשתנה. עברו בלולאה על שאר האיברים, ובכל פעם שאיבר גדול יותר מהמשתנה, שמרו אותו במקום זאת. כשהלולאה מסתיימת, המשתנה מכיל את הערך הגדול ביותר.
למה הערך המרבי המצטבר צריך להתחיל מהאיבר הראשון ולא מ־0?
אם כל הערכים שליליים, אף אחד מהם אינו גדול מ־0, ולכן ערך מרבי שמתחיל ב־0 לעולם אינו משתנה והפונקציה מחזירה 0. האיבר הראשון הוא תמיד מועמד אמיתי, ולכן התחלה ממנו נכונה לכל רשימה. גם המספר השלם הקטן ביותר בשפה שלך מתאים, כל עוד הרשימה אינה ריקה לעולם.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def findMax(nums):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
nums = [3, 17, 4, 12, 9]
הפלט הצפוי
17