Дан слайс целых чисел и число k. Выберите любые k элементов (разных по
позиции; значения могут совпадать) так, чтобы разница между максимальным и
минимальным из выбранных была наименьшей. Верните эту разницу.
(LeetCode 1984 Minimum Difference Between Highest and Lowest of K Scores.)
// MinRange возвращает минимум (max - min) по всем наборам из k элементов nums.
func MinRange(nums []int, k int) int
Примеры
[9, 4, 1, 7], k=2 → 2 // 7 и 9
[1, 5, 9, 2, 6], k=3 → 4 // 1, 2, 5
[3, 3, 10], k=2 → 0
[90], k=1 → 0
Ограничения
1 ≤ k ≤ len(nums) ≤ 10⁶, |nums[i]| ≤ 10¹⁸ — разность помещается в int
(64 бита).- Входной слайс не изменять.
- Ожидается O(n log n).
Устно: можно ли быстрее O(n log n)? Что изменится, если нужно вернуть сами
элементы?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.