Find Peak Element

Q: מהי סיבוכיות הזמן של Find Peak Element?

החיפוש הבינארי פועל בזמן O(log n) ובמרחב O(1) , לכל היותר 13 צעדים עבור 5000 ערכים. ההליכה משמאל היא O(n) , מכיוון שהיא עשויה לקרוא כל זוג לפני שהיא מוצאת את הירידה.

Q: האם החיפוש הבינארי עדיין עובד כשיש כמה פסגות?

כן, כל עוד שכנים שונים זה מזה והמיקומים שמעבר לשני הקצוות נחשבים לנמוכים מכל ערך. הפונקציה מחזירה פסגה אחת, לא תמיד את הגבוהה ביותר. אחרי עלייה, הערכים חייבים להתחיל לרדת עד סוף הטווח לכל המאוחר, והפנייה הראשונה היא פסגה, כך שהצד שהחיפוש ממשיך בו תמיד מכיל אחת.

Q: האם הפסגה היא תמיד הערך הגדול ביותר?

בבעיה הזו, כן: המערך עולה עד לשיא אחד ואז יורד אחריו, ולכן שום דבר אחר לא יכול להיות גדול יותר. בגרסה עם כמה שיאים זה לא כך, מכיוון שכל ערך שגדול משני שכניו נחשב. זו הסיבה שהחיפוש משווה בין שכנים במקום לחפש את הערך המרבי.

בינוניחיפוש בינארי

+10

המערך nums עולה ואז יורד: כל ערך גדול מהערך שלפניו עד לאינדקס מסוים, וכל ערך שאחריו קטן מהערך שלפניו. אחד החלקים יכול להיות ריק, ולכן המערך עשוי רק לעלות או רק לרדת. הערך באינדקס שבו הכיוון מתהפך הוא הפסגה, הערך היחיד שגדול מכל אחד משכניו.

החזר את האינדקס של הפסגה בזמן O(log n).

פונקציה

findPeakElement(nums: integer-array) → integer

numsinteger-array: הערכים עולים עד לשיא אחד ואז יורדים
מחזירהinteger: האינדקס של הפסגה

אילוצים

1 ≤ nums.length ≤ 5000
-10⁶ ≤ nums[i] ≤ 10⁶
nums[i] != nums[i+1] עבור כל i תקין.
nums עולה בקפדנות עד לאינדקס אחד ויורד בקפדנות אחריו, כך שיש בדיוק נקודת שיא אחת.

דוגמאות

קלט: nums = [2, 5, 9, 4, 1]
פלט: 2
הסבר: הערכים עולים דרך 2, 5 ו-9, ואז יורדים דרך 4 ו-1. נקודת המפנה היא ב-9, באינדקס 2.

שאלת המשך

ברשת שבה אין שני תאים סמוכים שווים, פסגה היא תא שגדול מארבעת שכניו לכל היותר. האם תוכלו למצוא אחת בלי לקרוא כל תא?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

עם שיא יחיד, השיא הוא הערך הגדול ביותר, ולכן מעבר אחד מוצא אותו ב־O(n). כדי להגיע ל־O(log n), השווה בין nums[mid] ל־nums[mid+1]: השיפוע ב־mid מראה באיזה צד של השיא הוא נמצא, כך שבכל צעד אפשר לצמצם את הטווח בחצי.

התקדם עד שהערכים יתחילו לרדת

האינטואיציה

לפני הפסגה, כל ערך קטן מהערך שאחריו, ומהפסגה ואילך כל ערך גדול מהערך שאחריו. לכן הפסגה היא האינדקס הראשון i שבו nums[i] > nums[i+1], או האינדקס האחרון אם המערך רק עולה.

כשהפסגה נמצאת בסוף של 5000 ערכים, המעבר מבצע 4999 השוואות, בעוד שחיפוש בינארי זקוק ל-13.

אלגוריתם

עבור i מ-0 עד n-2, השווה בין nums[i] לבין nums[i+1].
בפעם הראשונה שבה nums[i] גדול יותר, החזר את i.
אם הלולאה מסתיימת בלי ירידה, החזר את n-1.

def findPeakElement(nums):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            return i  # the first step down starts at the peak
    return len(nums) - 1  # never went down: the last value is the peak

חיפוש בינארי בשיפוע

האינטואיציה

קרא זוג אחד, nums[mid] ו-nums[mid+1]. צעד כלפי מעלה פירושו שהמערך עדיין מטפס, ובמערך הזה זה קורה רק לפני השיא: השיא נמצא ב-mid+1 או מימינו. צעד כלפי מטה פירושו שאתה בשיא או אחריו: השיא נמצא ב-mid או משמאלו.

שמור טווח [lo, hi] שתמיד מכיל את השיא. צעד כלפי מעלה מזיז את lo ל-mid+1. צעד כלפי מטה מזיז את hi ל-mid, ומשאיר את mid בטווח כי ייתכן שהוא השיא. כאשר lo ו-hi נפגשים, האינדקס היחיד שנותר הוא השיא. עיגול mid כלפי מטה משאיר אותו קטן מ-hi, ולכן mid+1 תמיד קיים.

בדוגמה הראשונה, mid = 2 רואה 9 > 4, לכן hi = 2; לאחר מכן mid = 1 רואה 5 < 9, לכן lo = 2, השיא. 5000 ערכים דורשים לכל היותר 13 צעדים.

אלגוריתם

הגדר את lo = 0 ואת hi = n-1.
כל עוד lo < hi, קח את mid = lo + (hi - lo) / 2, ועגל כלפי מטה.
אם nums[mid] < nums[mid+1], הגדר את lo = mid + 1.
אחרת, הגדר את hi = mid.
החזר את lo.

def findPeakElement(nums):
    lo, hi = 0, len(nums) - 1  # the peak is always inside [lo, hi]
    while lo < hi:
        mid = lo + (hi - lo) // 2  # mid < hi, so mid + 1 is a valid index
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1  # still climbing: the peak is to the right of mid
        else:
            hi = mid  # going down: the peak is mid or to its left
    return lo

מלכודות ומקרי קצה

הצבת hi = mid - 1 בצעד כלפי מטה. ב־[2, 5, 9, 4, 1] הערך הראשון של mid הוא נקודת השיא עצמה, ו־hi = 1 משליך אותה; החיפוש מחזיר 1.
השוואה עם nums[mid-1] תוך עיגול mid כלפי מטה. הערך של mid יכול להיות 0, ואז אין איבר שכן משמאל.
שימוש בטווח חצי פתוח עם hi = n. אז mid יכול להיות n-1, ו־nums[mid+1] ניגש מעבר לסוף, אפילו כשיש ערך יחיד.
שכחת ההזזה ב־Lua וב־R. התשובה עדיין תהיה האינדקס שמתחיל ב־0, ולכן המיקום i מוחזר בתור i-1.

שאלות נפוצות3

מהי סיבוכיות הזמן של Find Peak Element?

החיפוש הבינארי פועל בזמן O(log n) ובמרחב O(1), לכל היותר 13 צעדים עבור 5000 ערכים. ההליכה משמאל היא O(n), מכיוון שהיא עשויה לקרוא כל זוג לפני שהיא מוצאת את הירידה.

האם החיפוש הבינארי עדיין עובד כשיש כמה פסגות?

כן, כל עוד שכנים שונים זה מזה והמיקומים שמעבר לשני הקצוות נחשבים לנמוכים מכל ערך. הפונקציה מחזירה פסגה אחת, לא תמיד את הגבוהה ביותר. אחרי עלייה, הערכים חייבים להתחיל לרדת עד סוף הטווח לכל המאוחר, והפנייה הראשונה היא פסגה, כך שהצד שהחיפוש ממשיך בו תמיד מכיל אחת.

האם הפסגה היא תמיד הערך הגדול ביותר?

בבעיה הזו, כן: המערך עולה עד לשיא אחד ואז יורד אחריו, ולכן שום דבר אחר לא יכול להיות גדול יותר. בגרסה עם כמה שיאים זה לא כך, מכיוון שכל ערך שגדול משני שכניו נחשב. זו הסיבה שהחיפוש משווה בין שכנים במקום לחפש את הערך המרבי.

def findPeakElement(nums):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

nums = [2, 5, 9, 4, 1]

הפלט הצפוי