Вопрос:

Ссылка: https://leetcode.com/problems/kth-largest-element-in-a-stream/

Разработайте класс для поиска kth самого большого элемента в потоке. Обратите внимание, что это kth самый большой элемент в отсортированном порядке, а не kth отдельный элемент.

Реализовать класс KthLargest:

  • KthLargest(int k, int[] nums) Инициализирует объект целым числом k и потоком целых чисел nums.
  • int add(int val) Добавляет целое число val к потоку и возвращает элемент, представляющий kth самый большой элемент в потоке.

Пример 1:

Input
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output
[null, 4, 5, 5, 8, 8]
Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

Ограничения:

  • 1 <= k <= 104
  • 0 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • На номер add будет сделано не более 104 вызовов.
  • Гарантируется, что при поиске элемента kth в массиве будет не менее k элементов.

Решение:

Подход:

  1. Класс KthLargest имеет частную переменную экземпляра k, которая представляет значение K, и переменную PriorityQueue<Integer> с именем heap для хранения K самых больших элементов.
  2. Конструктор KthLargest(int k, int[] nums) вызывается для инициализации класса. Он принимает целое число k и массив nums в качестве входных данных.
  3. В конструкторе heap инициализируется как пустая очередь приоритетов.
  4. Затем код перебирает каждый элемент num в массиве nums и добавляет его в heap, используя метод add() приоритетной очереди. Это заполняет heap начальными элементами из массива.
  5. После добавления всех элементов код гарантирует, что heap содержит только K самых больших элементов. Он делает это, многократно вызывая метод poll() для heap, пока его размер не станет равным K. Это удаляет наименьшие элементы из heap, оставляя только K самых больших элементов.
  6. Метод add(int val) используется для добавления нового элемента val в структуру данных.
  7. В методе add() новый элемент добавляется в heap с помощью метода add() приоритетной очереди.
  8. После добавления нового элемента код проверяет, превышает ли размер heap K. Если это так, наименьший элемент удаляется из heap с помощью метода poll(). Это гарантирует, что heap поддерживает K самых больших элементов.
  9. Наконец, вызывается метод peek() класса heap для возврата текущего K-го по величине элемента.
class KthLargest {
    private static int k;
    private PriorityQueue<Integer> heap;
    
    public KthLargest(int k, int[] nums) {
        this.k = k;
        heap = new PriorityQueue<>();
        
        for (int num: nums) {
            heap.add(num);
        }
        
        while (heap.size() > k) {
            heap.poll();
        }
    }
    
    public int add(int val) {
        heap.add(val);
        if (heap.size() > k) {
            heap.poll();
        }

        return heap.peek();
    }
}

Временная сложность: O(logK)

Космическая сложность: O(K)

Заключение:

Надеюсь, что этот блог поможет вам решить вопрос, а также развеет ваши сомнения относительно решения. Пожалуйста, прокомментируйте, если вы знаете какие-либо новые подходы. Если у вас есть какие-либо сомнения, пожалуйста, прокомментируйте, и мы обсудим их.

Удачного кодирования.