Вопрос:
Ссылка: 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
элементов.
Решение:
Подход:
- Класс
KthLargest
имеет частную переменную экземпляраk
, которая представляет значение K, и переменнуюPriorityQueue<Integer>
с именемheap
для хранения K самых больших элементов. - Конструктор
KthLargest(int k, int[] nums)
вызывается для инициализации класса. Он принимает целое числоk
и массивnums
в качестве входных данных. - В конструкторе
heap
инициализируется как пустая очередь приоритетов. - Затем код перебирает каждый элемент
num
в массивеnums
и добавляет его вheap
, используя методadd()
приоритетной очереди. Это заполняетheap
начальными элементами из массива. - После добавления всех элементов код гарантирует, что
heap
содержит только K самых больших элементов. Он делает это, многократно вызывая методpoll()
дляheap
, пока его размер не станет равным K. Это удаляет наименьшие элементы изheap
, оставляя только K самых больших элементов. - Метод
add(int val)
используется для добавления нового элементаval
в структуру данных. - В методе
add()
новый элемент добавляется вheap
с помощью методаadd()
приоритетной очереди. - После добавления нового элемента код проверяет, превышает ли размер
heap
K. Если это так, наименьший элемент удаляется изheap
с помощью методаpoll()
. Это гарантирует, чтоheap
поддерживает K самых больших элементов. - Наконец, вызывается метод
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)
Заключение:
Надеюсь, что этот блог поможет вам решить вопрос, а также развеет ваши сомнения относительно решения. Пожалуйста, прокомментируйте, если вы знаете какие-либо новые подходы. Если у вас есть какие-либо сомнения, пожалуйста, прокомментируйте, и мы обсудим их.
Удачного кодирования.