Код Middle Два указателя обновлено
Минимальный разброс среди k чисел
Условие
Массив натуральных чисел, числа могут повторяться. Выбери k чисел так, чтобы разность максимального и минимального из выбранных была минимальной. Верни эту разность.
Примеры
minSpread(3, [10, 100, 300, 200, 1000, 20, 30]) // 20
minSpread(2, [100, 200, 300, 350, 400, 401, 402]) // 1
minSpread(4, [1, 2, 3, 4, 10, 20, 30, 40, 100, 200]) // 3
Как подойти
Ключевое наблюдение: в отсортированном массиве оптимальные k чисел обязательно образуют непрерывное окно - взять числа вразброс только увеличит разброс. Дальше один проход окном длины k. O(n log n) на сортировку. В коде с собеседования была ошибка: результат перезаписывался на каждой итерации вместо взятия минимума.
Подсказки: 2
- После сортировки нужные k чисел всегда идут подряд.
- Окно фиксированной длины k, разность концов - ответ.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.