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) Им...