स्ट्रीम लीटकोड सोल्यूशनमधील कॅथ सर्वात मोठे एलिमेंट


अडचण पातळी सोपे
वारंवार विचारले अडोब ऍमेझॉन सफरचंद बॉक्स हा कोड eBay फेसबुक गोल्डमन Sachs Google मायक्रोसॉफ्ट न्युटॅनिक्स
अल्गोरिदम डिझाईन ढीग

समस्या विधान

या समस्येमध्ये, आम्हाला एक क्लास डिझाइन करावा लागेल KthLargest () सुरुवातीला पूर्णांक के आणि एक आहे अॅरे पूर्णांक पूर्णांक के आणि अ‍ॅरे असल्यास त्या साठी पॅरामीटराइज्ड कन्स्ट्रक्टर लिहिण्याची गरज आहे संख्या वितर्क म्हणून पुरवले जातात. वर्ग देखील एक कार्य आहे जोडा (व्हॅल) हे व्हॅल्यूसह एक नवीन एलिमेंट जोडेल मूल्य पूर्णांक च्या प्रवाहात. प्रत्येकासाठी जोडा () कॉल करा, आपल्याला पूर्णांक मिळविणे आवश्यक आहे जो चालू असलेल्या प्रवाहातील सर्वात मोठा घटक आहे.

उदाहरण

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

स्पष्टीकरण:

स्ट्रीम लीटकोड सोल्यूशनमधील कॅथ सर्वात मोठे एलिमेंट

दृष्टीकोन (किमान ढीग)

जेव्हा जेव्हा Kth सर्वात लहान / सर्वात मोठा घटक शोधण्याची वेळ येते तेव्हा प्रत्येक वेळी जास्तीत जास्त / मिनिटांच्या ढीगांचा उद्देश असतो. हे त्यांच्या क्रमवारीनुसार (प्राधान्यकृत) फॅशनमध्ये घटक ठेवण्याच्या लवचिक स्वभावामुळे आहे. येथे जेव्हा आपण क्वेरी केली जाते तेव्हा घटक समाविष्ट करण्यासाठी अ‍ॅरे देखील वापरु शकलो असतो. पण, शोधण्यासाठी अ‍ॅरे मधील Kth सर्वात मोठा घटक, आम्हाला प्रत्येक क्वेरीसाठी ओ (एन) वेळ वापरणे आवश्यक आहे. म्हणून, आम्ही ओ (1) वेळेत सर्वात मोठा घटक शोधण्यासाठी, के आकाराचे किमान-ढीग ठेवू शकतो. लक्षात घ्या की आपण मि-हीप वापरत असल्यामुळे सर्वात मोठा घटक ढीगमध्ये सर्वात लहान असेल. आणि आम्ही प्रत्येक क्वेरीनंतर ढीग आकार के बरोबर समान असल्याचे बंधन घातले असल्याने, हा सर्वात मोठा घटक संपूर्ण प्रवाहात सर्वात मोठा Kth असेल (कारण ढीग केवळ के सर्वात मोठे घटक ठेवेल).

स्ट्रीम लीटकोड सोल्यूशनमध्ये कॅथ लार्ज एलिमेंटची अंमलबजावणी

सी ++ प्रोग्राम

#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;
}

जावा कार्यक्रम

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

स्ट्रीम लीटकोड सोल्यूशनमधील कॅथ सर्वात मोठ्या घटकाचे जटिल विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन + क्यू), जेथे N प्रारंभिक अ‍ॅरेचा आकार (कन्स्ट्रक्टरला कॉल करताना). Q = क्वेरींची संख्या. कारण आपण एकदा अ‍ॅरेचा आडवा घेतला आणि ओ (1) वेळेत प्रत्येक क्वेरीला उत्तर दिले.

स्पेस कॉम्प्लेक्सिटी 

ठीक आहे), जेथे K दिलेली युक्तिवाद आहे (कन्स्ट्रक्टरला कॉल करताना). हे असे आहे कारण कोणत्याही ऑपरेशननंतर आम्ही ढीग आकार अचूकपणे के.