ಸ್ಟ್ರೀಮ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ ಕೆಟಿ ಅತಿದೊಡ್ಡ ಅಂಶ  


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಆಪಲ್ ಬಾಕ್ಸ್ ಇಬೇ ಫೇಸ್ಬುಕ್ ಗೋಲ್ಡ್ಮನ್ ಸ್ಯಾಚ್ಸ್ ಗೂಗಲ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ನುಟಾನಿಕ್ಸ್
ಕ್ರಮಾವಳಿ ಅಲ್ಗಾರಿದಮ್ಗಳು ಕೋಡಿಂಗ್ ಡಿಸೈನ್ ರಾಶಿ ಸಂದರ್ಶನ ಸಂದರ್ಶನ ಪೂರ್ವಭಾವಿ ಲೀಟ್‌ಕೋಡ್ LeetCodeSolutions

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ  

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಾವು ವರ್ಗವನ್ನು ವಿನ್ಯಾಸಗೊಳಿಸಬೇಕು KthLargest () ಅದು ಆರಂಭದಲ್ಲಿ ಒಂದು ಪೂರ್ಣಾಂಕ k ಮತ್ತು an ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ ಸರಣಿ ಪೂರ್ಣಾಂಕಗಳ. ಒಂದು ಪೂರ್ಣಾಂಕ 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 ಅತಿದೊಡ್ಡ ಅಂಶ, ನಾವು ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ O (N) ಸಮಯವನ್ನು ಬಳಸಬೇಕಾಗುತ್ತದೆ. ಆದ್ದರಿಂದ, O (1) ಸಮಯದಲ್ಲಿ kth ಅತಿದೊಡ್ಡ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಾವು k ನ ಒಂದು ನಿಮಿಷದ ರಾಶಿಯನ್ನು ನಿರ್ವಹಿಸಬಹುದು. ನಾವು ನಿಮಿಷ-ರಾಶಿಯನ್ನು ಬಳಸುತ್ತಿರುವುದರಿಂದ, ಅಗ್ರಗಣ್ಯ ಅಂಶವು ರಾಶಿಯಲ್ಲಿ ಚಿಕ್ಕದಾಗಿದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಮತ್ತು ಪ್ರತಿ ಪ್ರಶ್ನೆಯ ನಂತರ ನಾವು ರಾಶಿ ಗಾತ್ರವನ್ನು k ಗೆ ಸಮನಾಗಿರುವುದರಿಂದ, ಈ ಉನ್ನತ ಅಂಶವು ಒಟ್ಟಾರೆ ಸ್ಟ್ರೀಮ್‌ನಲ್ಲಿ Kth ಅತಿದೊಡ್ಡದಾಗಿದೆ (ರಾಶಿ ಕೆ ಅತಿದೊಡ್ಡ ಅಂಶಗಳನ್ನು ಮಾತ್ರ ಇಡುತ್ತದೆ).

ಸಹ ನೋಡಿ
ನಿಧಾನಗತಿಯ ಕೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

ಸ್ಟ್ರೀಮ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದಲ್ಲಿ 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 ಅತಿದೊಡ್ಡ ಅಂಶದ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ + ಕ್ಯೂ)ಅಲ್ಲಿ N ಆರಂಭಿಕ ರಚನೆಯ ಗಾತ್ರ (ಕನ್‌ಸ್ಟ್ರಕ್ಟರ್‌ಗೆ ಕರೆ ಮಾಡುವಾಗ). Q = ಪ್ರಶ್ನೆಗಳ ಸಂಖ್ಯೆ. ಏಕೆಂದರೆ ನಾವು ಒಮ್ಮೆ ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ ಮತ್ತು ಪ್ರತಿ ಪ್ರಶ್ನೆಗೆ O (1) ಸಮಯದಲ್ಲಿ ಉತ್ತರಿಸುತ್ತೇವೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಸರಿ)ಅಲ್ಲಿ K ಕೊಟ್ಟಿರುವ ವಾದ (ಕನ್‌ಸ್ಟ್ರಕ್ಟರ್‌ಗೆ ಕರೆ ಮಾಡುವಾಗ). ಯಾವುದೇ ಕಾರ್ಯಾಚರಣೆಯ ನಂತರ ನಾವು ರಾಶಿ ಗಾತ್ರವನ್ನು ನಿಖರವಾಗಿ ಕೆ ಎಂದು ನಿರ್ವಹಿಸುತ್ತೇವೆ.

1