સ્ટ્રીમ લિટકોડ સોલ્યુશનમાં Kth સૌથી મોટું એલિમેન્ટ


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એડોબ એમેઝોન સફરજન બોક્સ ઇબે ફેસબુક ગોલ્ડમૅન સૅશ Google માઈક્રોસોફ્ટ ન્યુટનિક્સ
અલ્ગોરિધમ ડિઝાઇન .ગલો

સમસ્યા નિવેદન

આ સમસ્યામાં, અમારે વર્ગ ડિઝાઇન કરવો પડશે KthLargest () કે શરૂઆતમાં પૂર્ણાંક કે અને એન હોય છે એરે પૂર્ણાંકોની. પૂર્ણાંક કે અને એરે જ્યારે આપણે તેના માટે પેરામીટરાઇઝ્ડ કન્સ્ટ્રક્ટર લખવાની જરૂર છે સંખ્યા દલીલો તરીકે પસાર થાય છે. વર્ગ પણ એક કાર્ય છે ઉમેરો (વ valલ) જે મૂલ્ય સાથે એક નવું તત્વ ઉમેરશે Val પૂર્ણાંકોના પ્રવાહમાં. દરેક માટે ઉમેરો () ક callલ કરો, આપણે પૂર્ણાંક આપવું પડશે જે ચાલતા પ્રવાહમાં Kth સૌથી મોટો તત્વ છે.

ઉદાહરણ

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

સમજૂતી:

સ્ટ્રીમ લિટકોડ સોલ્યુશનમાં Kth સૌથી મોટું એલિમેન્ટ

અભિગમ (ન્યૂનતમ apગલા)

જ્યારે પણ તે Kth નાનું / સૌથી મોટું તત્વ શોધવાની વાત આવે છે, ત્યારે લગભગ દરેક વખતે મહત્તમ / મિનિટનો apગલો હેતુ પૂરો કરે છે. આ તત્વોને સ sર્ટ કરેલી (અગ્રતાવાળી) રાખવાની તેમની લવચીક પ્રકૃતિને કારણે છે. અહીં, જ્યારે પણ ક્વેરી બનાવવામાં આવે ત્યારે અમે તત્વોને સમાવવા માટે એરેનો ઉપયોગ કરી શકીએ છીએ. પરંતુ, ક્રમમાં શોધવા માટે એરેમાં Kth સૌથી મોટો તત્વ, આપણે દરેક ક્વેરી માટે ઓ (એન) સમયનો ઉપયોગ કરવો જ જોઇએ. તેથી, આપણે O (1) સમયમાં kth ના સૌથી મોટા તત્વને શોધવા માટે, કદ કદના મિનિ-apગલાને જાળવી શકીએ છીએ. નોંધ લો કે આપણે મિનિ-apગલાનો ઉપયોગ કરી રહ્યા છીએ, તેથી ટોચનું તત્વ mostગલામાં સૌથી નાનું હશે. અને કારણ કે આપણે દરેક ક્વેરી પછી theગલાના કદને k જેટલું બરાબર બાંધી દીધું છે, તેથી આ ટોચનું તત્વ એકંદર પ્રવાહમાં Kth સૌથી મોટું હશે (કારણ કે .ગલો ફક્ત k ના મોટા ભાગના તત્વો રાખે છે).

પ્રવાહ લીટકોડ સોલ્યુશનમાં 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 પ્રારંભિક એરે (કન્સ્ટ્રક્ટરને ક callingલ કરતી વખતે) નું કદ. Q = પ્રશ્નોની સંખ્યા. આ એટલા માટે છે કારણ કે આપણે એકવાર એરેને પસાર કરીએ છીએ અને દરેક ક્વેરીને ઓ (1) સમયમાં જવાબ આપીશું.

અવકાશ જટિલતા 

બરાબર)જ્યાં K આપેલ દલીલ છે (કન્સ્ટ્રક્ટરને ક callingલ કરતી વખતે). આ એટલા માટે છે કારણ કે આપણે કોઈ પણ setપરેશન પછી, afterગલો કદ બરાબર કે.