Дан слайс чисел nums и число k. Верните k самых больших чисел слайса
(с учётом повторов) в любом порядке. Решение через полную сортировку —
O(n log n); нужно обогнать его по асимптотике.
// TopK возвращает k наибольших элементов nums в любом порядке.
func TopK(nums []int, k int) []int
Примеры
nums = [105, 55, 5, 155, 105, 5, -25, 75], k = 3 → [155, 105, 105] (в любом порядке)
nums = [1, 2, 3], k = 0 → []
nums = [4, 4], k = 2 → [4, 4]
Ограничения
0 ≤ k ≤ len(nums) ≤ 10⁶, числа — любые int.- Входной слайс менять нельзя.
- Ожидается O(n log k) или O(n) в среднем. Расскажите, какой вариант лучше,
когда
k мало, а когда k ≈ n, и что делать, если данные идут потоком.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.