Kth Largest Element in an Array

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

מיון דורש זמן של O(n log n) . ערימת מינימום בגודל k דורשת זמן של O(n log k) וזיכרון של O(k) . ‏Quickselect עם ציר אקראי דורש זמן של O(n) בממוצע ו־ O(n²) במקרה הגרוע, שהסבירות לו נמוכה מאוד כשמשתמשים בציר אקראי.

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

הערימה שומרת את k הערכים הגדולים ביותר שנראו עד כה, והערך שעליך להשוות אליו ולסלק הוא הקטן ביותר מביניהם. ערימת מינימום שומרת את הערך הזה בראש. ערימת מקסימום עובדת רק אם מכניסים אליה את כל n הערכים ומוציאים איבר k-1 פעמים, דבר שדורש זיכרון O(n) .

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

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

בינוניערימה מיון

+10

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

ערכים שווים נספרים בנפרד. ב־[5, 5, 1] הערך הגדול ביותר הוא 5, וגם הערך השני בגודלו הוא 5.

פונקציה

findKthLargest(nums: integer-array, k: integer) → integer

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

אילוצים

1 ≤ k ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
ערכים שווים נספרים כערכים נפרדים.

דוגמאות

קלט: nums = [7, 2, 9, 4, 9, 1]k = 2
פלט: 9
הסבר: מהגדול לקטן, הערכים הם 9, 9, 7, 4, 2, 1. שתי הספרות 9 נספרות בנפרד, לכן הערך השני בגודלו הוא 9, ולא 7.

קלט: nums = [5, -3, 8, 0, 2]k = 4
פלט: 0
הסבר: מהגדול ביותר לקטן ביותר, הערכים הם 8, 5, 2, 0, -3, והרביעי מביניהם הוא 0.

קלט: nums = [6]k = 1
פלט: 6
הסבר: כשיש ערך אחד ו-k = 1, הערך הזה הוא הגדול ביותר.

+15 בדיקות נסתרות בשליחה

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

מיון וקריאה של מיקום אחד נותנים את התשובה, וזה מהיר מספיק כאן. מה שמראיין רוצה לראות הוא עד כמה אפשר לדלג על הסידור הזה, כי צריך מיקום אחד, ולא את כל n. ערימת מינימום בגודל k שומרת רק את הערכים שעדיין יכולים להיות התשובה, ו-quickselect מחלק למחיצות כמו quicksort אבל ממשיך רק לצד שמכיל את התשובה, וכך מוריד את זמן הריצה הממוצע ל-O(n).

מיון וקריאה של מיקום אחד

האינטואיציה

הערך ה־k בגודלו מוגדר לפי הסדר הממויין, לכן יש ליצור את הסדר הזה. במיון מהגדול לקטן, [7, 2, 9, 4, 9, 1] הופך ל־[9, 9, 7, 4, 2, 1], והערך ה־k בגודלו נמצא באינדקס k-1. עבור k = 2 זהו אינדקס 1, הערך 9 השני. אם המיון שלך מציב את הקטן ביותר ראשון, יש לקרוא במקום זאת את אינדקס n-k: אינדקס 4 של [1, 2, 4, 7, 9, 9] הוא אותו 9.

אין צורך בטיפול מיוחד בערכים כפולים: מיון שומר כל עותק, וכל עותק תופס מיקום משלו.

כאשר n = 10^4, מיון מבצע בערך n log n ≈ 1.3 × 10^5 השוואות, וזה עובר את כל הבדיקות. הבזבוז הוא שהוא מסדר את כל n הערכים, אף שרק מיקום אחד חשוב. שתי הגישות הבאות עושות פחות מהעבודה הזאת.

אלגוריתם

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

def findKthLargest(nums, k):
    # Largest first: the k-th largest sits at index k-1.
    ordered = sorted(nums, reverse=True)
    return ordered[k - 1]

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

האינטואיציה

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

כשמגיע ערך x והערימה מכילה פחות מ־k ערכים, מוסיפים אותו. אחרת משווים את x לערך שבראש הערימה. אם x אינו גדול ממנו, לפחות k ערכים ששמרת גדולים מ־x או שווים לו, ולכן x לעולם לא יכול להיות התשובה, ומדלגים עליו. אם x גדול ממנו, הערך שבראש הערימה יוצא מבין k הערכים הגדולים ביותר: מחליפים אותו ב־x. בדוגמה 2, כאשר k = 4, ארבעת הערכים הראשונים ממלאים את הערימה בערכים 5, -3, 8, 0, והערך שבראש הערימה הוא -3. לאחר מכן 2 גדול מ־-3 ומחליף אותו, הערך שבראש הערימה הופך ל־0, ו־0 הוא התשובה.

הטיפול בכל ערך דורש לכל היותר פעולת ערימה אחת בעלות O(log k), ולכן הסיבוכיות הכוללת היא O(n log k) בזמן ו־O(k) בזיכרון. השיטה יעילה ממיון כאשר k קטן, והיא מתאימה גם לזרם נתונים: לא צריך להחזיק את כל הערכים בו־זמנית. ל־Python יש heapq, ל־Java יש PriorityQueue, ל־C++ יש priority_queue עם greater, ל־Go יש container/heap, ל־Rust יש BinaryHeap עם Reverse, ול־PHP יש SplMinHeap. הקוד בשפות האחרות מממש את הערימה במערך, שבו הילדים של האינדקס i נמצאים באינדקסים 2i+1 ו־2i+2, או באינדקסים 2i ו־2i+1 ב־Lua וב־R, שבהן הספירה מתחילה ב־1.

אלגוריתם

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

import heapq


def findKthLargest(nums, k):
    # A min-heap of the k largest values so far; its top is the smallest of them.
    heap = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)  # drop the top, add x
    return heap[0]

בחירה מהירה עם חלוקה לשלושה חלקים

האינטואיציה

Quicksort בוחר ציר ומחלק: ערכים קטנים ממנו משמאלו, וערכים גדולים ממנו מימינו. לאחר חלוקה אחת הציר נמצא במקומו הסופי במערך הממויין, אף שאף אחד משני הצדדים עדיין לא ממויין. Quickselect משתמש בעובדה הזאת. בסדר מהקטן לגדול, התשובה נמצאת באינדקס target = n-k. אחרי חלוקה, target נמצא או משמאל לציר, או במיקום הציר, או מימינו, ולכן ממשיכים בצד אחד ומשליכים את השני.

עבור [7, 2, 9, 4, 9, 1] ו-k = 2, target הוא 6-2 = 4. מחלקים סביב 4: 2 ו-1 מקבלים את האינדקסים 0 ו-1, 4 מקבל את אינדקס 2, ו-7, 9, 9 מקבלים את האינדקסים 3 עד 5. אינדקס 4 נמצא מימין, ולכן משאירים רק את האינדקסים 3 עד 5. מחלקים אותם סביב 9: 7 מקבל את אינדקס 3 ושני ערכי ה-9 מקבלים את האינדקסים 4 ו-5. באינדקס 4 נמצא 9, ולכן התשובה היא 9.

השתמשו בחלוקה לשלושה חלקים: ערכים קטנים מהציר, אחריהם ערכים השווים לו, ואז ערכים גדולים ממנו, במעקב באמצעות lt ו-gt. מקטע הערכים השווים [lt, gt] נמצא במקומו הממויין, ולכן אם target נמצא בתוכו, סיימתם. בחלוקה רגילה לשני חלקים, מערך של 10^4 עותקים של 7 מצטמצם בערך אחד בכל סבב, כלומר כ-5 × 10^7 צעדים; הגרסה בעלת שלושת החלקים מוצאת את התשובה במעבר אחד.

בחרו את הציר באקראי. במחצית מהמקרים הוא נופל בחצי האמצעי של הטווח, וכך מצמצם את הטווח לכל היותר לשלושה רבעים מגודלו, ולכן העבודה הצפויה היא כמה מעברים על n ערכים: O(n). המקרה הגרוע ביותר עדיין O(n²) אם כל ציר הוא ערך קיצוני, ובחירה קבועה כמו האיבר הראשון מובילה לכך כאשר הקלט ממויין. הקוד עובד על עותק, שצורך זיכרון של O(n); חלוקה של nums עצמו מצמצמת את צריכת הזיכרון ל-O(1), אם מותר לשנות את הקלט.

אלגוריתם

העתק את nums אל a, הגדר target = n-k, את lo = 0 ואת hi = n-1.
בחר ציר אקראי מתוך a[lo..hi].
חלק את a[lo..hi] לערכים קטנים מהציר, שווים לו וגדולים ממנו, והשאר את הערכים השווים ב־a[lt..gt].
אם target < lt, הגדר hi = lt-1; אם target > gt, הגדר lo = gt+1; אחרת החזר את הציר.
חזור משלב 2.

import random


def findKthLargest(nums, k):
    a = list(nums)
    target = len(a) - k  # the answer's index once a is sorted smallest first
    lo, hi = 0, len(a) - 1
    while True:
        pivot = a[random.randint(lo, hi)]
        # Three-way partition of a[lo..hi]: < pivot, then == pivot, then > pivot.
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]
                gt -= 1
            else:
                i += 1
        # Now a[lt..gt] all equal pivot, and they are in their sorted places.
        if target < lt:
            hi = lt - 1
        elif target > gt:
            lo = gt + 1
        else:
            return pivot

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

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

הסרת כפילויות תחילה. הבעיה סופרת כל עותק: ב־[7, 2, 9, 4, 9, 1] עם k = 2 התשובה היא 9, אבל לאחר הפיכת המערך לקבוצה היא הופכת ל־7.
קריאת האינדקס הלא נכון. k נספר החל מ־1, לכן התשובה נמצאת באינדקס k-1 בסדר יורד ובאינדקס n-k בסדר עולה, ולא ב־n-k-1.
מיון מספרים כטקסט. ב־JavaScript וב־TypeScript, [10, 9, 2].sort() מחזיר [10, 2, 9]. העבירו (a, b) => a - b.
שימוש בערימת מקסימום בגודל k. הסרת הערך הגדול ביותר משאירה את k הערכים הקטנים ביותר ומחזירה את הערך הקטן ביותר ה־k.
שימוש ב־Quickselect עם חלוקה דו־כיוונית או ציר קבוע. ערכים שווים רבים או מערך ממוין גורמים לכך שהפעולה דורשת O(n²), וזה נכלל בבדיקות הגדולות.

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

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

מיון דורש זמן של O(n log n). ערימת מינימום בגודל k דורשת זמן של O(n log k) וזיכרון של O(k). ‏Quickselect עם ציר אקראי דורש זמן של O(n) בממוצע ו־O(n²) במקרה הגרוע, שהסבירות לו נמוכה מאוד כשמשתמשים בציר אקראי.

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

הערימה שומרת את k הערכים הגדולים ביותר שנראו עד כה, והערך שעליך להשוות אליו ולסלק הוא הקטן ביותר מביניהם. ערימת מינימום שומרת את הערך הזה בראש. ערימת מקסימום עובדת רק אם מכניסים אליה את כל n הערכים ומוציאים איבר k-1 פעמים, דבר שדורש זיכרון O(n).

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

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

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

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

nums = [7, 2, 9, 4, 9, 1]
k = 2

צפוי

Kth Largest Element in an Array

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

מיון וקריאה של מיקום אחד

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

בחירה מהירה עם חלוקה לשלושה חלקים

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

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

בעיות דומות