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

Задача с собеседования в eBay Дан массив целых чисел nums, сдвиньте его вправо на k шагов , где k - неотрицательное число. Follow up: - Постарайтесь придумать, как можно больше решений. Существует, по крайней мере, три разных способа решения этой задачи; - Можно ли решить задачу in-place, используя O(1) дополнительной памяти? Пример 1: Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] Explanation: сдвиг на один шаг вправо: [7, 1, 2, 3, 4, 5, 6] сдвиг на два шага вправо: [6, 7, 1, 2, 3, 4, 5] сдвиг на три шага вправо: [5, 6, 7, 1, 2, 3, 4] Пример 2: Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: сдвиг на один шаг вправо: [99, -1, -100, 3] сдвиг на два шага вправо: [3, 99, -1, -100] Ограничения: 1 <= nums.length <= 10⁵ -2³¹ <= nums[i] <= 2³¹ - 1 0 <= k <= 10⁵ НАШ ЧАТ АЛГОРИТМИСТОВ Решение Разберём один из способов решения этой задачи in-place - тройной разворот + метод двух указателей: Заметим, что массив nums как бы состоит из двух частей. Первая часть - числа, которые стоят в начале, но должны переместиться в конец, вторая часть - числа, которые находятся в конце, но должны уйти в начало. Алгоритм решения заключается в трёх разворотах. Перед началом разворотов выполняем k = k % len(nums) - это гарантирует корректный ответ, если k больше или равен длине массива. Так как сдвиг на len(nums) шагов оставляет массив неизменным, отбрасываем "полные круги" и выполняем только эффективные сдвиги - остаток от деления k на длину массива. Для визуализации рассмотрим работу алгоритма на примере 1 : 1. Переворачиваем первую часть: от нулевого индекса до len(nums) - k - 1 (так как кол-во эл-тов, которые должны переместиться в начало, равно k). [1,2,3,4,5,6,7] -> [4,3,2,1,5,6,7] 2. Переворачиваем вторую часть: от len(nums) - k до последнего эл-та массива. [4,3,2,1,5,6,7] -> [4,3,2,1,7,6,5] 3. И теперь переворачиваем весь массив целиком, чтобы разместить числа в правильном порядке. [4,3,2,1,7,6,5] -> [5,6,7,1,2,3,4] Чтобы избежать дублирования кода, создаём отдельный метод для реверсирования эл-тов через метод двух указателей: Пока l < r: - меняем местами число под индексом l с числом под индексом r; - двигаем левый указатель вправо, а правый указатель - влево. Этот метод отрабатывает в каждом из трёх разворотов. Делитесь вашим вариантом решения в комментариях! Сложность O(n) - время (где n - длина массива) O(1) - память (изменяем исходный массив без создания дополнительной структуры данных (in-place), используем две переменные: l и r) Код class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ k = k % len(nums) self.reverse(nums, 0, len(nums) - k - 1) self.reverse(nums, len(nums) - k, len(nums) - 1) self.reverse(nums, 0, len(nums) - 1) def reverse(self, nums: List[int], l: int, r: int) -> None: while l < r: nums[l], nums[r] = nums[r], nums[l] l += 1 r -= 1 @algoses