Median of Two Sorted Arrays

Q: מהי סיבוכיות הזמן של חציון של שני מערכים ממוינים?

החיפוש הבינארי בחיתוך אורך O(log(min(m, n))) וצורך O(1) מקום, כי בכל שלב מספר החיתוכים האפשריים ברשימה הקצרה יותר מצטמצם בחצי. מיזוג אורך O(m + n) : עבור שתי רשימות של 3000 איברים, כ־12 שלבים לעומת 6000.

Q: למה לבצע חיפוש בינארי במערך הקצר יותר?

מכיוון ש־ j = half-i . כש־ i נמצא בתחום הרשימה הקצרה יותר, j נשאר בין 0 לאורך הרשימה הארוכה יותר, כך שכל קריאה היא בטווח או מעבר לקצה שמתייחסים אליו כאינסוף.

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

+10

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

כשמספר הערכים הכולל אי־זוגי, החציון הוא הערך האמצעי, למשל "4". כשמספר הערכים זוגי, החציון הוא הממוצע של שני הערכים האמצעיים, למשל "2.5" או "-0.5". כתבו מספר שלם ללא נקודה עשרונית, ואת האפס כ־"0", לעולם לא כ־"-0". שאפו לזמן ריצה של O(log(min(m, n))).

פונקציה

findMedianSortedArrays(nums1: integer-array, nums2: integer-array) → string

nums1integer-array: הרשימה הראשונה, ממוינת מהקטן לגדול
nums2integer-array: הרשימה השנייה, ממוינת מהקטן לגדול
מחזירהstring: החציון של כל הערכים, כטקסט כגון "4" או "-2.5"

אילוצים

1 ≤ nums1.length, nums2.length ≤ 3000
-10⁶ ≤ nums1[i], nums2[i] ≤ 10⁶
שתי הרשימות ממוינות בסדר לא יורד, וערכים עשויים לחזור על עצמם.

דוגמאות

קלט: nums1 = [1, 4]nums2 = [2, 7, 9]
פלט: "4"
הסבר: יחד הערכים הם 1, 2, 4, 7, 9. כשיש חמישה ערכים, יש ערך אמצעי אחד, השלישי, והוא 4.

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

מיזוג הרשימות נותן את החציון ב־O(m + n), אבל רוב הערכים שהוא קורא אינם יכולים לשנות את התשובה. החציון תלוי רק במקום שבו עובר הגבול בין החצי התחתון לחצי העליון, ומספר אחד קובע את הגבול הזה: כמה ערכים החצי התחתון לוקח מהרשימה הקצרה יותר. חיפוש בינארי מוצא אותו ב־O(log(min(m, n))) צעדים.

מזג את שתי הרשימות

האינטואיציה

מזגו את הרשימות כפי שעושה מיון מיזוג, לרשימה ממוינת אחת merged. כאשר total = m + n, חברו את merged[(total-1)/2] ואת merged[total/2], תוך שימוש בחלוקה שלמה. כאשר הסכום הכולל אי־זוגי, שניהם הערך האמצעי, וכאשר הוא זוגי, אלה שני הערכים האמצעיים, ולכן מחצית הסכום היא החציון בכל מקרה.

גם אם עוצרים באמצע, שלבי המיזוג עוברים על יותר ממחצית הערכים, ולכן זמן הריצה הוא O(m + n).

אלגוריתם

מזגו את הרשימות לתוך merged, תוך בחירה תמיד בערך הנוכחי הקטן יותר, ואז בשארית הרשימה שנותרה.
כאשר total = m + n, הוסיפו את merged[(total-1)/2] ואת merged[total/2].
החזירו מחצית מהסכום כטקסט: חלקו סכום זוגי ב־2; עבור סכום אי־זוגי כתבו את הסימן, מחצית מהערך המוחלט ואת .5.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


def findMedianSortedArrays(nums1, nums2):
    # Merge the two sorted lists into one, the way merge sort does.
    merged = []
    i = j = 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            merged.append(nums1[i])
            i += 1
        else:
            merged.append(nums2[j])
            j += 1
    merged.extend(nums1[i:])
    merged.extend(nums2[j:])
    total = len(merged)
    # For an odd total both indexes point at the one middle value.
    return half_text(merged[(total - 1) // 2] + merged[total // 2])

חיפוש בינארי בנקודת החיתוך

האינטואיציה

נניח שבחצי התחתון יש half = (m+n+1)/2 ערכים, כולל הערך הנוסף כשהמספר הכולל אי־זוגי. נלקחים i ערכים מתחילת nums1 ו־j = half-i ערכים מתחילת nums2. החלוקה נכונה כששום ערך בחצי התחתון אינו גדול מאף ערך בחצי העליון. כל אחת מהרשימות ממוינת, ולכן נותרו שתי בדיקות: left1 ≤ right2 ו־left2 ≤ right1, כאשר left הוא הערך האחרון שרשימה מוסרת לחצי התחתון, ו־right הוא הערך הראשון שהיא משאירה. צד חסר נחשב למינוס או פלוס אינסוף.

אם left1 > right2, אז i גדול מדי; אם left2 > right1, הוא קטן מדי. לכן i הוא חיפוש בינארי בטווח שבין 0 ל־m. עבור [1, 2] ו־[3, 4], i = 1 נכשל כי left2 = 3 > right1 = 2, ו־i = 2 מצליח: (2 + 3) / 2 = 2.5.

אלגוריתם

הפוך את nums1 לרשימה הקצרה יותר; נגדיר half = (m+n+1)/2.
בצע חיפוש בינארי אחר i מ־lo = 0 עד hi = m, כאשר j = half-i.
קרא את left1 = nums1[i-1], את right1 = nums1[i], את left2 = nums2[j-1] ואת right2 = nums2[j], כאשר מעבר לקצה מציבים אינסוף.
אם left1 > right2, הצב hi = i-1. אם left2 > right1, הצב lo = i+1.
אחרת, אם הסכום הכולל אי־זוגי, החזר את max(left1, left2). אם הסכום הכולל זוגי, חלק את max(left1, left2) + min(right1, right2) ב־2 כטקסט.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


def findMedianSortedArrays(nums1, nums2):
    # Binary search over the shorter list.
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    m, n = len(nums1), len(nums2)
    half = (m + n + 1) // 2   # size of the left half; it gets the extra value when m + n is odd
    lo, hi = 0, m
    while lo <= hi:
        i = (lo + hi) // 2    # values the left half takes from nums1
        j = half - i          # values it takes from nums2
        # An empty side counts as minus or plus infinity.
        left1 = nums1[i - 1] if i > 0 else float("-inf")
        right1 = nums1[i] if i < m else float("inf")
        left2 = nums2[j - 1] if j > 0 else float("-inf")
        right2 = nums2[j] if j < n else float("inf")
        if left1 > right2:
            hi = i - 1        # too many values from nums1
        elif left2 > right1:
            lo = i + 1        # too few values from nums1
        else:
            left_max = max(left1, left2)
            if (m + n) % 2 == 1:
                return str(left_max)
            return half_text(left_max + min(right1, right2))
    return ""  # not reached: sorted input always has a valid split

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

חלוקה ב-2 עם נקודה צפה. Python מדפיסה חציון שלם בתור 3.0, ו-%f של C מדפיס 2.5 בתור 2.500000. השאר את הסכום כמספר שלם.
כתיבת המנה השלמה ו-.5 עבור סכום אי-זוגי שלילי. -1 / 2 הוא 0 ב-C וב-Java, ולכן מתקבל 0.5 עבור -0.5; -5 // 2 הוא -3 ב-Python, ולכן מתקבל -3.5 עבור -2.5. חלק את הערך המוחלט ב-2 והחזר את הסימן.
כתיבת -0. הערכים האמצעיים -1 ו-1 מסתכמים ב-0, והתשובה היא "0". קח את הסימן מהסכום.
חיפוש ברשימה הארוכה יותר. j = half-i יכול להיות קטן מ-0 או גדול מ-n. החלף בין הרשימות תחילה.
קריאת nums1[i-1] כאשר i = 0, כמו במקרה של [9] ו-[1, 2]. השתמש באינסוף עבור ערכים חסרים.

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

מהי סיבוכיות הזמן של חציון של שני מערכים ממוינים?

החיפוש הבינארי בחיתוך אורך O(log(min(m, n))) וצורך O(1) מקום, כי בכל שלב מספר החיתוכים האפשריים ברשימה הקצרה יותר מצטמצם בחצי. מיזוג אורך O(m + n): עבור שתי רשימות של 3000 איברים, כ־12 שלבים לעומת 6000.

למה לבצע חיפוש בינארי במערך הקצר יותר?

מכיוון ש־j = half-i. כש־i נמצא בתחום הרשימה הקצרה יותר, j נשאר בין 0 לאורך הרשימה הארוכה יותר, כך שכל קריאה היא בטווח או מעבר לקצה שמתייחסים אליו כאינסוף.

איך מחזירים את החציון בלי מספרים בנקודה צפה?

חברו את שני הערכים האמצעיים כמספרים שלמים. חלקו סכום זוגי ב־2. עבור סכום אי־זוגי, כתבו את מחצית הערך המוחלט שלו ואת .5, עם סימן מינוס כשהסכום שלילי: ‎-1 הופך ל־"-0.5".

def findMedianSortedArrays(nums1, nums2):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

nums1 = [1, 4]
nums2 = [2, 7, 9]

הפלט הצפוי

"4"