ഒരു സ്ട്രീം ലീറ്റ്കോഡ് പരിഹാരത്തിലെ ഏറ്റവും വലിയ ഘടകം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ആപ്പിൾ പെട്ടി ബെ ഫേസ്ബുക്ക് ഗോൾഡ്മാൻ സാക്സ് ഗൂഗിൾ മൈക്രോസോഫ്റ്റ് നൂതാനിക്സ്
അൽഗോരിതം ഡിസൈൻ കൂമ്പാരം

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ, ഞങ്ങൾ ഒരു ക്ലാസ് രൂപകൽപ്പന ചെയ്യണം KthLargest () തുടക്കത്തിൽ ഒരു സംഖ്യയും k ഉം ഉണ്ട് ശ്രേണി പൂർണ്ണസംഖ്യകളുടെ. ഒരു സംഖ്യ 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 ഏറ്റവും ചെറിയ / ഏറ്റവും വലിയ മൂലകം കണ്ടെത്തുമ്പോഴെല്ലാം, പരമാവധി / മിനിറ്റ് കൂമ്പാരങ്ങൾ മിക്കവാറും എല്ലാ സമയത്തും ഉദ്ദേശ്യത്തെ സഹായിക്കുന്നു. ഒരു അടുക്കിയ (മുൻ‌ഗണനാക്രമത്തിലുള്ള) ഘടകങ്ങൾ‌ കൈവശം വയ്ക്കുന്നതിനുള്ള സ flex കര്യപ്രദമായ സ്വഭാവമാണ് ഇതിന് കാരണം. ഇവിടെ, ഒരു ചോദ്യം ചോദിക്കുമ്പോഴെല്ലാം ഘടകങ്ങൾ ഉൾക്കൊള്ളാൻ ഞങ്ങൾക്ക് ഒരു അറേ ഉപയോഗിക്കാമായിരുന്നു. പക്ഷേ, കണ്ടെത്തുന്നതിന് അറേയിലെ ഏറ്റവും വലിയ മൂലകം, ഓരോ ചോദ്യത്തിനും O (N) സമയം ഉപയോഗിക്കേണ്ടതുണ്ട്. അതിനാൽ, O (1) സമയത്തിൽ kth ഏറ്റവും വലിയ മൂലകം കണ്ടെത്തുന്നതിന് നമുക്ക് k ന്റെ ഒരു ചെറിയ കൂമ്പാരം നിലനിർത്താൻ കഴിയും. ഞങ്ങൾ ഒരു മിൻ-ഹീപ്പ് ഉപയോഗിക്കുന്നതിനാൽ, ഏറ്റവും മുകളിലുള്ള ഘടകം കൂമ്പാരത്തിലെ ഏറ്റവും ചെറിയ ഘടകമാണെന്ന് ശ്രദ്ധിക്കുക. ഓരോ ചോദ്യത്തിനും ശേഷം ഞങ്ങൾ കൂമ്പാരത്തിന്റെ വലുപ്പം 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

ഒരു സ്ട്രീം ലീറ്റ്കോഡ് പരിഹാരത്തിലെ ഏറ്റവും വലിയ മൂലകത്തിന്റെ സങ്കീർണ്ണ വിശകലനം

സമയ സങ്കീർണ്ണത

O (N + Q)എവിടെ N = പ്രാരംഭ അറേയുടെ വലുപ്പം (കൺ‌സ്‌ട്രക്റ്ററെ വിളിക്കുമ്പോൾ). Q = ചോദ്യങ്ങളുടെ എണ്ണം. കാരണം, ഞങ്ങൾ ഒരു തവണ അറേയിലൂടെ സഞ്ചരിച്ച് ഓരോ ചോദ്യത്തിനും O (1) സമയത്തിനുള്ളിൽ ഉത്തരം നൽകുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത 

ശരി)എവിടെ K തന്നിരിക്കുന്ന ആർ‌ഗ്യുമെൻറ് (കൺ‌സ്‌ട്രക്റ്ററെ വിളിക്കുമ്പോൾ‌). ഏതെങ്കിലും കൂട്ടം പ്രവർത്തനങ്ങൾക്ക് ശേഷം, കൂമ്പാരത്തിന്റെ വലുപ്പം കൃത്യമായി k ആയി നിലനിർത്തുന്നതിനാലാണിത്.