Kth най-големият елемент в решение за поток Leetcode  


Ниво на трудност Лесно
Често задавани в Кирпич Амазонка ябълка Кутия иБей Facebook Goldman Sachs Google Microsoft Nutanix
алгоритъм алгоритми кодиране Дизайн купчина Интервю интерпретация LeetCode LeetCodeSolutions

Декларация за проблема  

В този проблем трябва да проектираме клас KthLargest () който първоначално има цяло число k и an масив на цели числа. Трябва да напишем параметризиран конструктор за него, когато е цяло число k и масив Nums се предават като аргументи. Класът също има функция добави (val) който добавя нов елемент със стойност вълна в потока от цели числа. За всеки добавяне () повикване, трябва да върнем цяло число, което е K-тият най-голям елемент в текущия поток.

Пример

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

Обяснение:

Kth най-големият елемент в решение за поток Leetcode

Подход (мин. Купчини)  

Винаги, когато става въпрос за намиране на Kth най-малкия / най-големия елемент, макс / мин купчини почти всеки път служат на целта. Това се дължи на гъвкавия им характер да съхраняват елементи по сортиран (приоритизиран) начин. Тук бихме могли да използваме и масив, който да съдържа елементите, когато се прави заявка. Но, за да се намери Kth най-големият елемент в масива, трябва да използваме O (N) време за всяка заявка. Следователно можем да поддържаме минимална купчина с размер k, за да намерим k-тия най-голям елемент за O (1) време. Имайте предвид, че тъй като използваме min-heap, най-горният елемент ще бъде най-малкият в купчината. И тъй като ние обвързахме размера на купчината да бъде равен на k след всяка заявка, този горен елемент ще бъде K-тият по големина в общия поток (тъй като купчината ще запази само k-големи елементи).

Вижте също
Най-бавно решение с Leetcode

Внедряване на 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

Анализ на сложността на Kth най-големия елемент в решение за поток Leetcode

Сложност във времето

O (N + Q), Където N = размер на първоначалния масив (при извикване на конструктора). Q = Брой заявки. Това е така, защото обхождаме масива веднъж и отговаряме на всяка заявка за O (1) време.

Сложност на пространството 

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

Вижте също
Извършете низови смени Leetcode