Kth Largest Element in a Stream

Q: למה להשתמש בערימת מינימום ולא בערימת מקסימום כדי למצוא את האיבר ה־k בגודלו?

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

Q: מהי סיבוכיות הזמן של האיבר ה־K בגודלו בזרם?

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

קלערימה

+10

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

ב־nums יש לפחות k-1 ערכים, כך שלאחר ההגעה הראשונה תמיד יש לפחות k ערכים לבחירה.

פונקציה

kthLargestStream(k: integer, nums: integer-array, adds: integer-array) → integer-array

kinteger: הדירוג לדיווח, 1 עבור הערך הגדול ביותר
numsinteger-array: הערכים שכבר נמצאים בזרם
addsinteger-array: הערכים שמגיעים, לפי הסדר
מחזירהinteger-array: הערך ה־k בגודלו לאחר כל הגעה

אילוצים

1 ≤ nums.length ≤ 10⁴
1 ≤ adds.length ≤ 10⁴
1 ≤ k ≤ nums.length + 1
-10⁴ ≤ nums[i], adds[i] ≤ 10⁴
nums יכול להיות בכל סדר, וערכים שווים נחשבים לערכים נפרדים.

דוגמאות

קלט: k = 3nums = [7, 1, 5]adds = [3, 9, 6, 2, 8]
פלט: [3, 5, 6, 6, 7]
הסבר: אחרי 3 מגיע השלישי בגודלו מבין 7, 5, 3 ו-1, והוא 3. אחר כך 9 מעלה אותו ל-5, 6 מעלה אותו ל-6, 2 לא משנה דבר, ו-8 מעלה אותו ל-7 (9, 8, 7).

קלט: k = 1nums = [-2]adds = [-5, 0, -1, 4]
פלט: [-2, 0, 0, 4]
הסבר: כאשר k = 1, התשובה היא הערך הגדול ביותר עד כה: ‎-2 עד שמגיע 0, עדיין 0 אחרי ‎-1, ואז 4.

שאלת המשך

איך היית עונה על אותה שאלה אם היה אפשר גם להסיר ערכים מהזרם?

רמזים

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

נפתחו 0 מתוך 3

פתרון

ערכים לעולם אינם יוצאים מהזרם, ולכן ערך שיורד מתחת לערך ה־k בגודלו הנוכחי יוצא ממנו לתמיד. שמור רק את k הערכים הגדולים ביותר בערימת מינימום: הערך שבראשה הוא התשובה, וכל ערך שמגיע דורש השוואה אחת ולכל היותר עדכון אחד של הערימה בזמן O(log k).

מיין אחרי כל הגעה

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

שמור כל ערך ברשימה. אחרי כל הוספה, מיין אותה בסדר עולה וקרא את האינדקס length-k, שהוא לפי ההגדרה האיבר ה־k בגודלו.

כל הוספה ממיינת עד n + m ערכים, כאשר n ו־m הם האורכים של nums ו־adds. עם 10^4 מכל אחד, מדובר בכ־2 × 10^9 השוואות בסך הכול.

אלגוריתם

העתק את nums לרשימה values.
עבור כל ערך של adds, הוסף אותו אל values.
מיין את values בסדר עולה ותעד את values[length-k].
החזר את הערכים שתועדו.

def kthLargestStream(k, nums, adds):
    values = list(nums)
    result = []
    for x in adds:
        values.append(x)
        values.sort()
        # In increasing order the k-th largest sits k places from the end.
        result.append(values[len(values) - k])
    return result

ערימת מינימום של k הערכים הגדולים ביותר

האינטואיציה

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

כש־x מגיע והערימה מלאה, השווה אותו לאיבר העליון. אם x אינו גדול יותר, הוא אינו בין k הערכים הגדולים ביותר ושום דבר לא משתנה. אם הוא גדול יותר, האיבר העליון יוצא: החלף אותו ב־x והעבר אותו כלפי מטה בערימה, בזמן O(log k). הערכים ההתחלתיים עוברים את אותה שגרה, ולכן nums עשוי להיות ארוך מ־k.

בדוגמה הראשונה, הערימה מכילה את 7, 1 ו־5 אחרי nums, כאשר 1 נמצא בראש. הערך 3 שמגיע מחליף את 1, והאיבר העליון, 3, הוא התשובה הראשונה.

אלגוריתם

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

import heapq


def kthLargestStream(k, nums, adds):
    # A min-heap of the k largest values so far; heap[0] is the smallest of them.
    heap = []

    def add(x):
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x

    for x in nums:
        add(x)
    result = []
    for x in adds:
        add(x)
        result.append(heap[0])  # the k-th largest so far
    return result

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

הסרת כפילויות. ארבעת הערכים הגדולים ביותר מבין 9, 6, 6, 6, 2 הם 9, 6, 6 ו-6. קבוצה, או בדיקה שמדלגת על ערכים שכבר קיימים, מחזירה 2 בדוגמה השלישית במקום 6.
קריאת התשובה לפני ההוספה. כאשר nums מכיל k-1 ערכים, הערימה מלאה רק לאחר הוספת הערך הראשון, לכן הוסיפו קודם ורק אז קראו את הערך העליון.
ספירה מהקצה הלא נכון לאחר מיון. בסדר עולה, הערך הגדול ה-k נמצא באינדקס length-k; באינדקס k-1 נמצא הערך הקטן ה-k.
שימוש בסדר ברירת המחדל של הערימה. priority_queue של C++ ו-BinaryHeap של Rust הן ערימות מקסימום: העבירו את greater<int> או עטפו את הערכים ב-Reverse.

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

למה להשתמש בערימת מינימום ולא בערימת מקסימום כדי למצוא את האיבר ה־k בגודלו?

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

מהי סיבוכיות הזמן של האיבר ה־K בגודלו בזרם?

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

האם אפשר לפתור את בעיית האיבר ה־K בגודלו בזרם באמצעות רשימה ממוינת?

כן. שמור את כל הערכים ממוינים, הכנס כל ערך שמגיע למקומו באמצעות חיפוש בינארי, וקרא את הערך שנמצא k מקומות מהסוף. החיפוש הוא O(log n), אבל הזזת הערכים שאחרי נקודת ההכנסה היא O(n) לכל ערך שמגיע: בערך 1.5 × 10^8 הזזות עבור 10^4 ערכי התחלה ו־10^4 ערכים שמגיעים.

def kthLargestStream(k, nums, adds):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

k = 3
nums = [7, 1, 5]
adds = [3, 9, 6, 2, 8]

הפלט הצפוי

[3, 5, 6, 6, 7]