ஸ்ட்ரீம் லீட்கோட் தீர்வில் Kth மிகப்பெரிய உறுப்பு


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் பெட்டி ஈபே பேஸ்புக் கோல்ட்மேன் சாக்ஸ் கூகிள் மைக்ரோசாப்ட் Nutanix
அல்காரிதம் வடிவமைப்பு குவியல்

சிக்கல் அறிக்கை

இந்த சிக்கலில், நாங்கள் ஒரு வகுப்பை வடிவமைக்க வேண்டும் KthLargest () ஆரம்பத்தில் ஒரு முழு எண் k மற்றும் ஒரு உள்ளது வரிசை முழு எண்களின். ஒரு முழு எண் k மற்றும் வரிசை இருக்கும்போது நாம் அதற்கு ஒரு அளவுருவாக்கப்பட்ட கட்டமைப்பாளரை எழுத வேண்டும் எண்கள் வாதங்களாக அனுப்பப்படுகின்றன. வகுப்பிற்கும் ஒரு செயல்பாடு உள்ளது சேர் (வால்) இது மதிப்புடன் புதிய உறுப்பைச் சேர்க்கிறது வால் முழு எண்களின் நீரோட்டத்தில். ஒவ்வொரு கூட்டு() அழைப்பு, இயங்கும் ஸ்ட்ரீமில் 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) நேரத்தைப் பயன்படுத்த வேண்டும். ஆகையால், 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

ஒரு ஸ்ட்ரீம் லீட்கோட் தீர்வில் Kth மிகப்பெரிய உறுப்பின் சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

O (N + Q), எங்கே N ஆரம்ப வரிசையின் அளவு (கட்டமைப்பாளரை அழைக்கும் போது). Q = வினவல்களின் எண்ணிக்கை. ஏனென்றால், நாங்கள் வரிசையை ஒரு முறை கடந்து, ஒவ்வொரு வினவலுக்கும் O (1) நேரத்தில் பதிலளிக்கிறோம்.

விண்வெளி சிக்கலானது 

சரி), எங்கே K கொடுக்கப்பட்ட வாதம் (கட்டமைப்பாளரை அழைக்கும் போது). ஏனென்றால், எந்தவொரு செயல்பாட்டிற்கும் பிறகு, குவியல் அளவை சரியாக k ஆக பராமரிக்கிறோம்.