एक स्ट्रीम Leetcode समाधान में Kth सबसे बड़ा तत्व  


कठिनाई स्तर आसान
में अक्सर पूछा एडोब वीरांगना सेब मुक्केबाज़ी ईबे Facebook गोल्डमैन सैक्स गूगल माइक्रोसॉफ्ट Nutanix
कलन विधि एल्गोरिदम कोडिंग डिज़ाइन ढेर साक्षात्कार साक्षात्कार की तैयारी लेटकोड लेटकोड सॉल्यूशंस

समस्या का विवरण  

इस समस्या में, हमें एक वर्ग डिजाइन करना होगा KthLargest () शुरू में एक पूर्णांक k और a है सरणी पूर्णांकों का। जब एक पूर्णांक k और सरणी होता है, तो हमें इसके लिए एक पैरामीटर निर्मित निर्माता लिखने की आवश्यकता होती है nums तर्क के रूप में पारित किया जाता है। क्लास का भी एक फंक्शन है जोड़ें (वैल) जो मान के साथ एक नया तत्व जोड़ता है लहर पूर्णांकों की धारा में। प्रत्येक के लिए (जोड़ें) कॉल करें, हमें एक पूर्णांक वापस करने की आवश्यकता है जो कि रनिंग स्ट्रीम में Kth सबसे बड़ा तत्व है।

उदाहरण

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

स्पष्टीकरण:

एक स्ट्रीम Leetcode समाधान में Kth सबसे बड़ा तत्वपिन

दृष्टिकोण (न्यूनतम हेड्स)  

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

यह भी देखें
सबसे धीमी कुंजी Leetcode समाधान

एक स्ट्रीम लेकोडकोड समाधान में Kth सबसे बड़े तत्व का कार्यान्वयन

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 = प्रश्नों की संख्या। ऐसा इसलिए है क्योंकि हम एक बार सरणी को पार कर लेते हैं और प्रत्येक प्रश्न का उत्तर O (1) समय में देते हैं।

अंतरिक्ष जटिलता 

ठीक है), जहां K दिया गया तर्क (निर्माणकर्ता को कॉल करते समय) है। ऐसा इसलिए है क्योंकि हम किसी भी संचालन के बाद, ढेर के आकार को ठीक-ठीक कश्मीर के बराबर बनाए रखते हैं।

1