Kth најголем елемент во проток на решение за код за код  


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон Јаболко кутија eBay Facebook Голдман Сакс Google Мајкрософт Нутаникс
Алгоритам алгоритми кодирање дизајн Грамада интервју интервју подготви 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

објаснување:

Kth најголем елемент во проток на решение за код за кодПин

Пристап (мин. Грамада)  

Кога и да станува збор за наоѓање на Kth најмал / најголем елемент, макс / мин грамада скоро секој пат служат за целта. Ова е заради нивната флексибилна природа да држат елементи на сортиран (приоритетен) начин. Тука, можевме да користиме низа за да ги содржиме елементите кога и да се постави барање. Но, со цел да се најде Kth најголем елемент во низата, мора да користиме O (N) време за секое барање. Затоа, можеме да одржиме мин-грамада со големина k, за да го најдеме најголемиот kth во О (1) време. Забележете дека бидејќи користиме мин-грамада, највисокиот елемент би бил најмалиот во грамадата. И бидејќи ја ограничивме големината на грамадата да биде еднаква на k по секое барање, овој врвен елемент ќе биде Kth најголем во вкупниот тек (бидејќи грамадата ќе ги задржи k најголемите елементи само).

Видете исто така
Најспоро клучно решение за леткод

Имплементација на најголемиот елемент 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

Анализа на комплексноста на најголемиот елемент Kth во проток на решение за леткод

Временска комплексност

O (N + Q), Каде што N = големина на почетната низа (при повик кон конструкторот). Q = Број на пребарувања. Ова е затоа што еднаш ја пресекуваме низата и одговараме на секое барање во време О (1).

Комплексноста на просторот 

ДОБРО), Каде што K е дадениот аргумент (при повик кон конструкторот). Ова е затоа што ја одржуваме големината на грамадата точно k, по кој било сет на операции.

1