Find Median from Data Stream

Q: מהי סיבוכיות הזמן של Find Median from Data Stream?

עם שתי ערימות, addNum היא O(log n) , לכל היותר שלוש פעולות הוספה לערימה או הוצאה ממנה, ו- findMedian היא O(1) , שתי קריאות. כל הערכים נשמרים, ולכן המקום הוא O(n) . מיון בכל שאילתה עולה במקום זאת O(n log n) לכל findMedian .

Q: למה לא לשמור את הערכים במערך ממוין?

מערך ממוין מחזיר תשובה עבור findMedian ב־ O(1) , וחיפוש בינארי מוצא היכן ערך חדש נכנס ב־ O(log n) . אבל הכנסתו מזיזה כל ערך שאחריו, O(n) לכל addNum .

קשהערימה

+10

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

פעולה i היא ops[i], כאשר values[i] מכיל את המספר עבור addNum ואת 0 עבור findMedian. הרץ אותן לפי הסדר על מבנה ריק והחזר מחרוזת אחת עבור כל פעולה: "null" עבור addNum, ואת החציון עבור findMedian. כתוב את החציון כך: "3", "2.5" או "-0.5": ללא נקודה עשרונית עבור מספר שלם, ואפס כ-"0", לעולם לא "-0".

פונקציה

medianStreamOps(ops: string-array, values: integer-array) → string-array

opsstring-array: הפעולות, לפי סדר ביצוען
valuesinteger-array: המספר עבור כל addNum, 0 עבור כל findMedian
מחזירהstring-array: תשובה אחת לכל פעולה, כטקסט

אילוצים

1 ≤ ops.length ≤ 3000
values.length == ops.length
כל ops[i] הוא addNum או findMedian.
-10⁵ ≤ values[i] ≤ 10⁵ עבור addNum, ו־values[i] == 0 עבור findMedian.
findMedian נקראת רק אחרי לפחות קריאה אחת ל־addNum.

דוגמאות

קלט: ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]values = [5, 0, 1, 0, 8, 0, 3, 0]
פלט: ["null", "5", "null", "3", "null", "5", "null", "4"]
הסבר: עם 1 ו־5 החציון הוא (1 + 5) / 2 = 3. עם 1, 5 ו־8 הוא 5, ועם 1, 3, 5 ו־8 הוא (3 + 5) / 2 = 4.

שאלת המשך

אם כל הערכים היו בין 0 ל־100, איך היית יכול לגרום לשתי הפעולות לפעול בזמן קבוע?

רמזים

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

נפתחו 0 מתוך 3

פתרון

החציון נמצא בין שני חצאי הנתונים, ולכן הסדר בתוך כל חצי אינו משנה: רק הערך הגדול ביותר בחצי התחתון והערך הקטן ביותר בחצי העליון חשובים. שתי ערימות שומרות בדיוק את שני הערכים האלה בראשן. כל addNum עולה O(log n), וכל findMedian קוראת את שני הערכים שבראש הערימות בזמן O(1).

מיון בכל findMedian

האינטואיציה

שמור כל ערך ברשימה. findMedian ממיינת אותה וקוראת את האינדקסים (total-1)/2 ו־total/2, בחלוקה שלמה: אותו אינדקס כשמספר הערכים אי־זוגי, ואת הזוג האמצעי כשמספרם זוגי. חבר את שני הערכים וחלק את הסכום בשניים, וכך תקבל את החציון בשני המקרים.

חלק באמצעות מספרים שלמים. סכום זוגי מתחלק בדיוק. סכום אי־זוגי הופך למחצית הערך המוחלט שלו ואחריה .5, עם הסימן של הסכום, כך ש־-3 הופך ל־-1.5.

כל שאילתה ממיינת מחדש. עם 1,500 פעולות הוספה ושאילתה אחרי כל אחת מהן, מדובר בכ־10^7 השוואות, בעוד שהערמות זקוקות לכמה עשרות אלפי צעדים.

אלגוריתם

החזק רשימה של values.
עבור addNum x, הוסף את x ותעד "null".
עבור findMedian, מיין את values והוסף את values[(total-1)/2] ואת values[total/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"


class MedianFinder:
    def __init__(self):
        self.values = []

    def addNum(self, x):
        self.values.append(x)

    def findMedian(self):
        self.values.sort()
        total = len(self.values)
        # For an odd count both indexes point at the one middle value.
        return half_text(self.values[(total - 1) // 2] + self.values[total // 2])


def medianStreamOps(ops, values):
    finder = MedianFinder()
    result = []
    for op, x in zip(ops, values):
        if op == "addNum":
            finder.addNum(x)
            result.append("null")
        else:
            result.append(finder.findMedian())
    return result

שתי ערימות המופרדות בחציון

האינטואיציה

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

ערך חדש נכנס ל־low אם הוא קטן או שווה לערך שבראש low; אחרת, הוא נכנס ל־high. כשהגדלים יוצאים מאיזון, מעבירים ערך שבראש ערימה אחת לערימה האחרת: זהו הערך הקרוב ביותר לחצי השני, ולכן הסדר נשמר. הוספה דורשת כמה פעולות ערימה, O(log n), או O(n) ב־R, שמעתיקה את הערימה בכל שינוי.

אחרי ארבע ההוספות בדוגמה הראשונה, low מכיל את 3 ואת 1, ו־high מכיל את 5 ואת 8.

אלגוריתם

שמרו ערמת מקסימום בשם low עבור החצי התחתון וערמת מינימום בשם high עבור החצי העליון.
addNum x: הכניסו את x אל low אם low ריקה או אם x קטן או שווה לאיבר העליון שלה, אחרת הכניסו אותו אל high.
אם יש ב-low שני ערכים יותר מאשר ב-high, העבירו את האיבר העליון של low אל high. אם יש ב-high יותר ערכים מאשר ב-low, העבירו את האיבר העליון של high אל low.
findMedian: אם low גדולה יותר, שמרו את האיבר העליון שלה. אחרת, חברו את שני האיברים העליונים וחלקו את הסכום בשתיים באמצעות חילוק של מספרים שלמים.

import heapq


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"


class MedianFinder:
    def __init__(self):
        self.low = []   # the smaller half; heapq is a min-heap, so it stores -x to keep the largest on top
        self.high = []  # the larger half, smallest on top

    def addNum(self, x):
        if not self.low or x <= -self.low[0]:
            heapq.heappush(self.low, -x)
        else:
            heapq.heappush(self.high, x)
        # Rebalance: low holds as many values as high, or one more.
        if len(self.low) > len(self.high) + 1:
            heapq.heappush(self.high, -heapq.heappop(self.low))
        elif len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def findMedian(self):
        if len(self.low) > len(self.high):
            return str(-self.low[0])
        return half_text(-self.low[0] + self.high[0])


def medianStreamOps(ops, values):
    finder = MedianFinder()
    result = []
    for op, x in zip(ops, values):
        if op == "addNum":
            finder.addNum(x)
            result.append("null")
        else:
            result.append(finder.findMedian())
    return result

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

בחירת הערימה לפי הגודל במקום לפי הערך. הוספה לערימה הקטנה יותר בלי להשוות מפרה את הסדר בין שני החצאים, וראשי הערימות מפסיקים להיות הערכים האמצעיים.
חלוקה לשניים באמצעות חלוקה שלמה רגילה. ב-C וב-Java, -1 / 2 הוא 0, ולכן הוספת .5 מדפיסה 0.5 עבור -0.5. ב-Python, -3 // 2 הוא -2, ולכן מתקבל -2.5 עבור -1.5. בחלק מהשפות, מספרים בנקודה צפה מודפסים כ-3.0 או כ-2.500000.
אחסון low כשהוא שלילי בערימת מינימום, ושכחה להפוך את הסימן בחזרה כשקוראים את ראש הערימה או מעבירים ערך אל high.
כתיבת -0. הערכים האמצעיים -1 ו-1 מסתכמים ב-0, והתשובה היא "0".

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

מהי סיבוכיות הזמן של Find Median from Data Stream?

עם שתי ערימות, addNum היא O(log n), לכל היותר שלוש פעולות הוספה לערימה או הוצאה ממנה, ו-findMedian היא O(1), שתי קריאות. כל הערכים נשמרים, ולכן המקום הוא O(n). מיון בכל שאילתה עולה במקום זאת O(n log n) לכל findMedian.

למה לא לשמור את הערכים במערך ממוין?

מערך ממוין מחזיר תשובה עבור findMedian ב־O(1), וחיפוש בינארי מוצא היכן ערך חדש נכנס ב־O(log n). אבל הכנסתו מזיזה כל ערך שאחריו, O(n) לכל addNum.

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

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

def medianStreamOps(ops, values):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

ארגומנטים

ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]
values = [5, 0, 1, 0, 8, 0, 3, 0]

הפלט הצפוי

["null", "5", "null", "3", "null", "5", "null", "4"]