האלמנט הגדול ביותר של Kth בפתרון Stream Leetcode


רמת קושי קַל
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ אריזה מקורית eBay פייסבוק גולדמן זאקס Google מיקרוסופט נוטניקס
אַלגוֹרִיתְם עיצוב ערימה

הצהרת בעיה

בבעיה זו עלינו לעצב כיתה KthLargest () שיש בהתחלה מספר שלם k ו- מערך של מספרים שלמים. עלינו לכתוב עבור זה קונסטרוקטור פרמטריאלי כאשר מספר שלם k ומערך Nums מועברים כוויכוחים. לשיעור יש גם פונקציה הוסף (val) שמוסיף אלמנט חדש עם ערך val לזרם המספרים השלמים. לכל אחד הוסף () אנו חייבים להחזיר מספר שלם שהוא האלמנט הגדול ביותר Kth בזרם הרץ.

דוגמה

["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
4 5 5 8 8

הסבר:

האלמנט הגדול ביותר של Kth בפתרון Stream Leetcode

גישה (מיני ערמות)

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

יישום האלמנט הגדול ביותר Kth בפתרון Leetcode Stream

תוכנית C ++

#include <bits/stdc++.h>

using namespace std;

class KthLargest {
public:
    priority_queue <int , vector <int> , greater <int> > pq;
    int K;

    KthLargest(int k, vector<int>& nums) {
        K = k;
        for(int &x : nums) {
            pq.push(x);
            if(pq.size() > k) {
                pq.pop();
            }
        }
    }

    int add(int val) {
        pq.push(val);
        if(pq.size() > K)
            pq.pop();
        return pq.top();
    }
};

int main() {
    vector <int> nums = {4 , 5 , 8 , 2};
    int k = 3;
    KthLargest stream(k , nums);
    cout << stream.add(3) << " ";
    cout << stream.add(5) << " ";
    cout << stream.add(10) << " ";
    cout << stream.add(9) << " ";
    cout << stream.add(4) << " ";
    cout << endl;
    return 0;
}

תוכנית Java

import java.util.*;
import java.io.*;

class comp implements Comparator<Integer> {
    public int compare(Integer a , Integer b) {
        if(a > b)
            return 1;
        if(a < b)
            return -1;
        return 0;
    }
}

class KthLargest {
    int K;
    PriorityQueue <Integer> pq;

    public KthLargest(int k, int[] nums) {
        K = k;
        pq = new PriorityQueue <Integer> (new comp());
        for(int x : nums) {
            pq.add(x);
            if(pq.size() > k) {
                pq.remove();
            }
        }
    }

    int add(int val) {
        pq.add(val);
        if(pq.size() > K)
            pq.remove();
        return pq.peek();
    }
}

class KthLargestInStream {
    public static void main(String args[]) {
        int k = 3;
        int[] nums = {4 , 5 , 8 , 2};
        KthLargest stream = new KthLargest(k , nums);
        System.out.print(stream.add(3) + " ");
        System.out.print(stream.add(5) + " ");
        System.out.print(stream.add(10) + " ");
        System.out.print(stream.add(9) + " ");
        System.out.print(stream.add(4) + " ");
        System.out.println();
    }
}
4 5 5 8 8

ניתוח מורכבות של האלמנט הגדול Kth בפתרון Leetcode זרם

מורכבות זמן

O (N + Q), שם N = גודל המערך הראשוני (תוך כדי קריאה לבנאי). Q = מספר השאילתות. הסיבה לכך היא שאנחנו חוצים את המערך פעם אחת ועונים על כל שאילתה בזמן O (1).

מורכבות בחלל 

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