K-й самый большой элемент в решении Stream Leetcode  


Сложный уровень Легко
Часто спрашивают в саман Амазонка Apple Коробка eBay Facebook Goldman Sachs Google Microsoft Nutanix
Алгоритм алгоритмы кодирование Дизайн куча Интервью подготовка к собеседованию LeetCode LeetCodeSolutions

Постановка задачи  

В этой задаче мы должны спроектировать класс KthLargest () который изначально имеет целое число k и массив целых чисел. Нам нужно написать параметризованный конструктор для него, когда целое число k и массив НУМС передаются как аргументы. В классе также есть функция добавить (val) который добавляет новый элемент со значением волна в поток целых чисел. Для каждого Добавить() вызов, нам нужно вернуть целое число, которое является K-м по величине элементом в текущем потоке.

Пример

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

Объяснение:

K-й самый большой элемент в решении Stream Leetcodeшпилька

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

Всякий раз, когда дело доходит до нахождения K-го наименьшего / наибольшего элемента, кучи max / min почти всегда служат этой цели. Это связано с их гибкостью, позволяющей хранить элементы в отсортированном (приоритетном) виде. Здесь мы также могли бы использовать массив для хранения элементов всякий раз, когда выполняется запрос. Но, чтобы найти K-й по величине элемент в массиве, мы должны использовать время O (N) для каждого запроса. Следовательно, мы можем поддерживать минимальную кучу размера k, чтобы найти k-й по величине элемент за время O (1). Обратите внимание: поскольку мы используем минимальную кучу, самый верхний элемент будет наименьшим в куче. И поскольку мы ограничили размер кучи равным k после каждого запроса, этот верхний элемент будет K-м по величине в общем потоке (поскольку куча будет содержать только k самых больших элементов).

Смотрите также
Самое медленное ключевое решение Leetcode

Реализация K-го крупнейшего элемента в решении Stream 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

Анализ сложности K-го наибольшего элемента в решении Stream Leetcode

Сложность времени

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

Космическая сложность 

ОК), Где K - заданный аргумент (при вызове конструктора). Это потому, что мы поддерживаем размер кучи ровно k после любого набора операций.

1