Задача с собеседования в Josh Technology

Задача с собеседования в Josh Technology Обмен определяется как выбор двух различных позиций в массиве и перестановка их значений местами. Круговой массив определяется как массив, в котором первый и последний элементы считаются соседними . Дан бинарный круговой массив nums. Верните минимальное количество обменов, необходимых для того, чтобы сгруппировать все 1, присутствующие в массиве, вместе в любом месте. Пример 1: Input: nums = [0,1,0,1,1,0,0] Output: 1 Explanation: Есть несколько способов сгруппировать все 1 вместе: [0,0,1,1,1,0,0] с использованием 1 обмена. [0,1,1,1,0,0,0] с использованием 1 обмена. [1,1,0,0,0,0,1] с использованием 2 обменов (используя круговое свойство массива). Не существует способа сгруппировать все 1 вместе, не выполнив ни одного обмена. Таким образом, минимальное необходимое количество обменов - 1. Пример 2: Input: nums = [0,1,1,1,0,0,1,1,0] Output: 2 Explanation: Есть несколько способов сгруппировать все 1 вместе: [1,1,1,0,0,0,0,1,1] с использованием 2 обменов (используя круговое свойство массива). [1,1,1,1,1,0,0,0,0] с использованием 2 обменов. Не существует способа сгруппировать все 1 вместе с использованием 0 или 1 обменов. Таким образом, минимальное необходимое количество обменов - 2. Пример 3: Input: nums = [1,1,0,0,1] Output: 0 Explanation: Все 1 уже сгруппированы вместе, учитывая круговое свойство массива. Таким образом, минимальное количество обменов - 0. Ограничения: 1 <= nums.length <= 10⁵ nums[i] равно 0 или 1. НАШ ЧАТ АЛГОРИТМИСТОВ Решение Обратим внимание, что кол-во единиц, которые нужно сгруппировать, фиксировано и равняется общему кол-ву единиц в массиве (total_ones). Так как единицы могут быть разбросаны по массиву, необходимо проверить каждый подмассив длиной total_ones и определить среди них тот, в котором уже находится максимальное кол-во единиц (а следовательно потребуется меньше обменов). => Кол-во необходимых обменов равняется кол-ву нулей в подмассиве с максимумом единиц (кол-во нулей = total_ones - максимальное кол-во единиц в окне). Чтобы избежать повторного подсчёта нулей в подмассиве, используем метод "скользящего окна" с двумя указателями. total_ones - размер окна (определяем методом count()) window_ones - счётчик единиц в текущем окне max_window_ones - лучший результат по кол-ву единиц в окне l - левая граница окна r - правая граница окна Если общее кол-во единиц в массиве равно 1 или 0: - возвращаем 0, так как группировать нечего. Для корректной обработки окон в циклическом массиве - проходим 2n итераций, беря индексы по модулю (% n), что позволит вернуться в начало при выходе за правую границу. Проходим по массиву правым указателем: - Добавляем правый эл-т в окно. - Если длина окна превысила total_ones: - убираем один эл-т слева; - сдвигаем l вправо. - Обновляем max_window_ones. Возвращаем ответ как разность между общим кол-вом единиц и кол-вом единиц в наиболее «единичном» окне. Сложность O(n) - по времени (проходим 2n итераций, константа отбрасывается) O(1) - по памяти (храним некоторое кол-во переменных) Код class Solution: def minSwaps(self, nums: list[int]) -> int: n = len(nums) total_ones = nums.count(1) if total_ones <= 1: return 0 l = 0 window_ones = max_window_ones = 0 for r in range(n * 2): window_ones += nums[r % n] if r - l + 1 > total_ones: window_ones -= nums[l % n] l += 1 max_window_ones = max(max_window_ones, window_ones) return total_ones - max_window_ones Оптимизация Решение можно оптимизировать, сохранив текущую асимптотику: Так как размер окна фиксирован (total_ones), можем обойтись без левого указателя: считаем кол-во единиц в первом окне, а затем проходим по массиву, совершая n сдвигов. На каждой итерации прибавляем входящий эл-т и вычитаем уходящий. Проверка на превышение длины окна не требуется. Кол-во операций сократится до n (сдвиги) + total_ones (построение первого окна). Пишите оптимизированный вариант кода в комментариях! @algoses