Ағынның ағынды кодының ең үлкен элементі


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon алма қорап еВау Facebook Голдман Сакс Google Microsoft Нутаниx
Алгоритм жобалау Үйінді

Проблемалық мәлімдеме

Бұл мәселеде біз сыныпты жобалауымыз керек KthLargest () басында k және an бүтін саны бар массив бүтін сандар. Біз оған бүтін k және массив кезінде параметрленген конструктор жазуымыз керек сансыз аргумент ретінде беріледі. Сыныптың да қызметі бар қосу (вал) бұл мәні бар жаңа элемент қосады Val бүтін сандар ағынына. Әрқайсысы үшін қосу () қоңырау шалыса, біз ағындағы ең үлкен K элемент болатын бүтін санды қайтаруымыз керек.

мысал

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

Түсіндіру:

Ағынның ағынды кодының ең үлкен элементі

Тәсіл (мин үйінділері)

Kth ең кіші / ең үлкен элементті табу туралы болған сайын, max / min үйінділері мақсатқа әр уақытта қызмет етеді. Бұл олардың икемділік сипатына байланысты, элементтерді сұрыпталған (басымдылық) күйде ұстайды. Мұнда біз сұраныс жасалған кезде элементтерді қамтитын массив қолданған болар едік. Бірақ, табу үшін Массивтегі ең үлкен элемент, біз әр сұраныс үшін O (N) уақытын пайдалануымыз керек. Сондықтан, O (1) уақыттағы k-ші ең үлкен элементті табу үшін k өлшемді мин-үйіндісін сақтай аламыз. Біз мин-үйінді қолданып жатқандықтан, ең жоғарғы элемент үйіндідегі ең кіші болатынын ескеріңіз. Біз үйінді мөлшерін әрбір сұраудан кейін k-ге тең етіп байлап қойғандықтан, бұл жоғарғы элемент жалпы ағынның ішіндегі K-ші үлкен болады (өйткені үйінді тек ең үлкен элементтерді сақтайтын болады).

Kth ең үлкен элементін ағынды Leetcode ерітіндісінде енгізу

C ++ бағдарламасы

#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;
}

Java бағдарламасы

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

Ағындық Leetcode ерітіндісіндегі Kth ең үлкен элементтің күрделілігін талдау

Уақыттың күрделілігі

O (N + Q), мұндағы N = бастапқы массивтің өлшемі (конструкторды шақыру кезінде). Q = Сұрақтар саны. Себебі, біз массивті бір рет айналып өтіп, O (1) уақытта әрбір сұрауға жауап береміз.

Ғарыштың күрделілігі 

ЖАРАЙДЫ МА), мұндағы K берілген аргумент болып табылады (конструкторды шақыру кезінде). Себебі, біз кез-келген амалдар жиынтығынан кейін үйінді мөлшерін дәл k деп ұстаймыз.