স্ট্রিম লেটকোড সলিউশনে Kth বৃহত্তম এলিমেন্ট  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় রৌদ্রপক্ব ইষ্টক মর্দানী স্ত্রীলোক আপেল বক্স ইবে ফেসবুক গোল্ডম্যান শ্যাস গুগল মাইক্রোসফট Nutanix
অ্যালগরিদম আলগোরিদিম আইনসংগ্রহ নকশা গাদা সাক্ষাত্কার সাক্ষাৎকারের প্রস্তুতি লেটকোড LeetCodeSolutions

সমস্যা বিবৃতি  

এই সমস্যায়, আমাদের একটি ক্লাস ডিজাইন করতে হবে কেথলার্জেস্ট () যে প্রাথমিকভাবে একটি পূর্ণসংখ্যা k এবং একটি আছে বিন্যাস পূর্ণসংখ্যার একটি পূর্ণসংখ্যা k এবং অ্যারে যখন আমাদের এটির জন্য একটি প্যারামিটারাইজড কনস্ট্রাক্টর লিখতে হবে নাম্বার যুক্তি হিসাবে পাস করা হয়। ক্লাসের একটি ফাংশনও রয়েছে যোগ (ভাল) যা মান সহ একটি নতুন উপাদান যুক্ত করে Val পূর্ণসংখ্যার প্রবাহে into প্রতিটির জন্য, প্রত্যেকটির জন্য যোগ করুন () কল করুন, আমাদের একটি পূর্ণসংখ্যা ফেরত পাঠানো দরকার যা চলমান প্রবাহের কেথ বৃহত্তম বৃহত্তম উপাদান।

উদাহরণ

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

ব্যাখ্যা:

স্ট্রিম লেটকোড সলিউশনে Kth বৃহত্তম এলিমেন্টপিন

পদ্ধতির (ন্যূনতম গাদা)  

যখনই এটি Kth বৃহত্তম / বৃহত্তম উপাদান সন্ধান করতে আসে, সর্বাধিক / মিনিটের হিপগুলি প্রায় প্রতিবারই উদ্দেশ্যটি পরিবেশন করে। এটি তাদের সাজানো (অগ্রাধিকারযুক্ত) ফ্যাশনে উপাদানগুলি ধরে রাখার নমনীয় প্রকৃতির কারণে। এখানে, আমরা যখনই কোনও জিজ্ঞাসা করা হয় তখন উপাদানগুলি রাখতে একটি অ্যারে ব্যবহার করতে পারতাম। তবে, এটি সন্ধান করার জন্য অ্যারের মধ্যে Kth বৃহত্তম উপাদান, প্রতিটি কোয়েরির জন্য আমাদের অবশ্যই ও (এন) সময় ব্যবহার করতে হবে। অতএব, আমরা ও (1) সময়ে কেথের বৃহত্তম এলিমেন্টটি খুঁজে পেতে, আকারের কে ন্যূনতম গাদা রাখতে পারি। নোট করুন যেহেতু আমরা একটি মিনিট-হিপ ব্যবহার করছি তাই শীর্ষস্থানীয় উপাদানটি গাদাতে সবচেয়ে ছোট হবে। এবং যেহেতু আমরা প্রতিটি ক্যোয়ারির পরে স্তূপের আকার কে সমান করে বেঁধেছি, এই শীর্ষ উপাদানটি সামগ্রিক স্ট্রিমের কেথ বৃহত্তম হবে (যেহেতু গাদা কেবল কে বৃহত্তম উপাদান রাখবে)।

আরো দেখুন
সবচেয়ে ধীর কী লেটকোড সমাধান

স্ট্রিম লেটকোড সমাধানে কেথ লার্জ এলিমেন্টের প্রয়োগ

সি ++ প্রোগ্রাম

#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) সময়ে প্রতিটি প্রশ্নের উত্তর দিই।

স্পেস জটিলতা ity 

ঠিক আছে), কোথায় K প্রদত্ত আর্গুমেন্ট (কনস্ট্রাক্টরকে কল করার সময়)। এটি কারণ যে কোনও ক্রিয়াকলাপের পরে আমরা হিপ আকারটি ঠিক কে হিসাবে রাখতে পারি।

1