Ctrl K

Ряд без пропусков

Сложная
Дан массив целых чисел values длины n. Назовём его **сплошным**, если в нём все числа различны и после сортировки идут подряд без пропусков, то есть максимум минус минимум равен n - 1. Например, [6, 4, 5, 7] — сплошной, а [1, 2, 4] — нет. За одну операцию можно заменить любой элемент на любое целое число. Верните наименьшее число операций, после которых массив станет сплошным.
Пример 1
values=[3, 8, 4, 4, 6] → 2

Меняем вторую четвёрку на 5, а 8 на 7: получаем [3, 7, 4, 5, 6] — числа от 3 до 7 без повторов.

Пример 2
values=[1, 100, 200] → 2

Любые два из трёх чисел слишком далеко друг от друга, сохранить можно только одно.

Пример 3
values=[10] → 0
Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиМедиана разнообразия отрезков СложнаяДва отрезка с нужной суммой СредняяСнять с краёв ровно столько СредняяОдинаковые подряд после удалений СредняяМедиана в скользящем окне Сложная
загружаем Python…
Вход
values=[3, 8, 4, 4, 6]
Ожидается
2

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 134 теста на сервере, включая скрытые.