Kth найбільший елемент у рішенні Leetcode Stream  


Рівень складності Легко
Часто запитують у саман Амазонка Apple Box eBay Facebook Goldman Sachs Google Microsoft Нутанікс
Алгоритм алгоритми кодування дизайн купа інтерв'ю інтерв'юпідготовка LeetCode LeetCodeSolutions

Постановка проблеми  

У цій задачі ми повинні розробити клас KthLargest () що спочатку має ціле число k та an масив цілих чисел. Нам потрібно написати параметризований конструктор для нього, коли ціле число k і масив чисел передаються як аргументи. Клас також має функцію додати (val) що додає новий елемент зі значенням Val у потік цілих чисел. Для кожного add () виклику, нам потрібно повернути ціле число, яке є K-м найбільшим елементом у поточному потоці.

Приклад

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

Пояснення:

Kth найбільший елемент у рішенні Leetcode StreamPin

Підхід (мінімальна купа)  

Щоразу, коли йдеться про пошук K-го найменшого / найбільшого елемента, макс. / Хв відвали майже кожного разу слугують цілі. Це пов’язано з їх гнучкою природою зберігати елементи впорядковано (за пріоритетом). Тут ми могли б також використовувати масив, щоб містити елементи при кожному запиті. Але для того, щоб знайти K-й найбільший елемент у масиві, ми повинні використовувати O (N) час для кожного запиту. Отже, ми можемо підтримувати мінімальну купу розміром k, щоб знайти k-й найбільший елемент за час O (1). Зверніть увагу, що оскільки ми використовуємо min-heap, найвищий елемент буде найменшим у купі. І оскільки ми обмежили розмір кучі рівним k після кожного запиту, цей верхній елемент буде K-м найбільшим у загальному потоці (оскільки купа зберігатиме лише k найбільших елементів).

Дивись також
Найповільніше рішення Leetcode

Реалізація Kth найбільшого елемента в рішенні Leetcode Stream

Програма С ++

#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 після будь-якого набору операцій.

1