Агымдын Leitcode чечиминдеги ири элемент  


Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon алма кутуча Окшош Facebook Goldman Sachs Гугл Microsoft Nutanix
Algorithm Алгоритмы коддоо дизайн Куча интервью интервью даярдоо LeetCode 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

Explanation:

Агымдын Leitcode чечиминдеги ири элементтөөнөч

Ыкма (Мин үймөктөр)  

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

ошондой эле
Акырын Leetcode чечими

Агым Leetcode чечиминде Kth ири элементин ишке ашыруу

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) убакытта ар бир суроого жооп беребиз.

Космостун татаалдыгы 

O (K)кайда K берилген аргумент болуп саналат (конструкторду чакырып жатканда). Себеби, биз ар кандай операциялардан кийин үймөктүн көлөмүн так к деп сактайбыз.

1