Сообщения

Показаны сообщения с ярлыком "Кучи"

k-й наибольший элемент в массиве

Источник: https://leetcode.com/problems/kth-largest-element-in-an-array/ Дан массив целых чисел nums и целое число k , вернуть k -й наибольший элемент в массиве , как сли бы массив был отсортирован. Задачу нужно решить за O(n) . Пример 1: Дано: nums = [3,2,1,5,6,4], k = 2 Результат: 5 Пример 2: Дано : nums = [3,2,3,1,2,4,5,5,6], k = 4 Результат: 4   Ограничения: 1 <= k <= nums.length <= 10 5 -10 4   <= nums[i] <= 10 4 Идея решения 1 Будем использовать кучу с наименьшим элементом в вершине, ограничив размер кучи числом k. Добавляя все элементы в массиве, один за другим, как только мы превысим размер кучи, то удалим наименьший элемент. Таким образом, в куче будет всегда находиться  k наибольших элементов. После обработки всего массива, k-й наибольший элемент будет находится в вершине кучи. Сложность алгоритма: добавление в кучу размера k занимает O(log k). мы добавляем N элментов в кучу, где N - размер массива. Итого общая сложность = O(N log k) Им...

k самых частых элементов

Источник: https://leetcode.com/problems/top-k-frequent-elements/ Дан массив целых чисел nums и число k , вернуть   k самых частых элементов . Самые частые элементы можно вернуть в любом порядке. Пример 1: Дано: nums = [1,1,1,2,2,3], k = 2 Результат: [1,2] Пример 2: Дано: nums = [1], k = 1 Результат: [1] Ограниечения: 1 <= nums.length <= 10 5 k в интервале [1, число уникальных жлементов в массиве] . Изветно, что решение существует и уникально . Алгоритм должен быть быстрее O(n log n) , где n - размер массива (то есть обойтись без сортировки).   Имплементация class Solution {     public int[] topKFrequent(int[] nums, int k) {         // O(1) time         if (k == nums.length) {             return nums;         }               ...

Найти медиану среди элементов потока данных

 Источник: https://leetcode.com/problems/find-median-from-data-stream/ Медиана - это значение, которое находится в середине отсортированного списка целых чисел. Если размер списка четный, то медиана - это среднее арифметическое двух элементов из середины списка. Например, для arr = [2,3,4] , медиана = 3 . Для arr = [2,3] , медиана = (2 + 3) / 2 = 2.5 . Заимплементировать класс MedianFinder такой, что: MedianFinder()   iинициализирует объект MedianFinder . void addNum(int num) добавляет целое число num из потока данных в структуру данных. double findMedian() возвращает медиану полученных данных на текущий момент.  Пример 1: Дано ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] Результат [null, null, null, 1.5, null, 2.0] Пояснение MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] me...