स्ट्रीम लेटकोड समाधानमा Kth सबैभन्दा ठूलो एलिमेन्ट


कठिनाई तह सजिलो
बारम्बार सोधिन्छ एडोब अमेजन एप्पल पेटी eBay फेसबुक Goldman सैक्स गुगल माइक्रोसफ्ट नुटानिक्स
अल्गोरिदम डिजाइन ढेर

समस्या वक्तव्य

यो समस्यामा हामीले कक्षा कोर्नु पर्छ KthLargest () सुरुमा इन्टिजर k र an हुन्छ array पूर्णांकको। हामीले यसको लागि प्यारामेराइज्ड कन्स्ट्रक्टर लेख्न आवश्यक पर्दछ जब एक पूर्णांक k र एर्रे संख्या तर्कको रूपमा पारित गरियो। कक्षाको पनि फंक्शन छ थप्नुहोस् (भेल) त्यो मानको साथ एक नयाँ तत्व जोड्दछ Val पूर्णांकको प्रवाहमा। प्रत्येकको लागी थप्नुहोस् () कल, हामीले एक पूर्णांक फिर्ता गर्न आवश्यक छ जुन चलिरहेको स्ट्रिममा Kth सब भन्दा ठूलो एलिमेन्ट हो।

उदाहरणका

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

व्याख्या:

स्ट्रीम लेटकोड समाधानमा Kth सबैभन्दा ठूलो एलिमेन्ट

दृष्टिकोण (न्यूनतम ढेर)

जब यो Kth सब भन्दा सानो / सबै भन्दा ठूलो तत्व पत्ता लगाउन आउँछ, अधिकतम / मिनेट हिप्स प्रायः प्रत्येक पटक उद्देश्यको लागि सेवा गर्दछ। यो किनभने क्रमबद्ध (प्राथमिकता) फेसनमा तत्वहरू समात्नको तिनीहरूको लचिलो प्रकृति हो। यहाँ, हामी पनि एर्रे प्रयोग गर्न सक्दछ एन्टिमेन्टहरू समावेश गर्न को लागी जब पनि क्वेरी बनाइन्छ। तर, फेला पार्नको लागि एर्रेमा Kth सबैभन्दा ठूलो एलिमेन्ट, हामीले प्रत्येक क्वेरीका लागि O (N) समय प्रयोग गर्नुपर्दछ। तसर्थ, हामी आकार क k को एक न्यूनतम ढिलाई कायम राख्न सक्छौं, O (१) समयमा kth सबैभन्दा ठूलो तत्व फेला पार्न। नोट गर्नुहोस् कि हामी एक मिनेट-हीप को उपयोग गरीरहेको छ, शीर्ष को तत्व तत्व ढेर मा सानो छ। र जब हामी हिप साइज प्रत्येक क्वेरी पछाडि k को बराबरको सीमामा बाँध्छौं, यो शीर्ष तत्व समग्र स्ट्रिममा Kth सबैभन्दा ठूलो हुन्छ (किनकि यस ढेरले k मात्र सबैभन्दा ठूलो तत्त्वहरू राख्दछ)।

स्ट्रीमको लेटकोड समाधानमा क्याथ सबैभन्दा ठूलो एलिमेन्टको कार्यान्वयन

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

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

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

स्ट्रीम लीटकोड समाधानमा क्याथ सबैभन्दा ठूलो एलिमेन्टको जटिलता विश्लेषण

समय जटिलता

O (N + Q)जहाँ N = प्रारम्भिक एर्रेको आकार (कन्स्ट्रक्टरलाई कल गर्दा)। Q = प्रश्नहरूको संख्या। यो किनभने हामी एक पटक एर्रे पार गर्दछौं र प्रत्येक क्वेरीलाई ओ (१) समयमा जवाफ दिन्छौं।

ठाउँ जटिलता 

ठिक छ)जहाँ K दिइएको आर्गुमेन्ट हो (कन्स्ट्रक्टरलाई कल गर्दा)। यो किनभने हामी हिप साइज ठ्याक्कै क, हुनका लागि राख्छौं कुनै अपरेशन्सको सेट पछि।