UniLecs #Task. Shift array

Albert Davletov

Published in

UniLecs

2 min readDec 29, 2019

Задача: дан массив целых чисел, необходимо сделать сдвиг элементов вправо на K шагов.

Входные данные: arr — массив натуральных чисел, размер массив от 1 до 10⁶, K — натуральное число от 0 до 10⁶.

Вывод: преобразованный массив

Условие: для преобразования использовать только исходный массив.

Пример:

1. Arr = [1, 2, 3, 4, 5]; K = 3;

Output: [3, 4, 5, 1, 2]

2. Arr = [-5, -11, 0, 9, 3]; K = 2;

Output: [9, 3, -5, -11, 0]

Разбор

Для начала заметим, что сдвиг элементов массива Arr на K, равному размеру исходного массива, не изменит положение элементов. Очевидно, что и для любого K кратному размеру исходного массива. То есть для случаев, где K % Arr.Length == 0, мы можем сразу возвращать исходный массив.

Для полноты решения приведем разбор с использованием вспомогательного массива. В этом случае мы просто перебираем элементы массива и записываем каждый из них в новый массив с новым индексом. Индекс сдвига мы определяем по следующей формуле: (i + K) % Arr.Length, где i — индекс элемента в исходном массиве.

Решение без использования вспомогательного массива несколько сложнее. Сложность в том, что на каждом шаге нам нужно хранить элемент, ктр мы затираем.
Алгоритм следующий:

В цикле перебираем все элементы массива
Фиксируем текущий элемент и его индекс.
Запустим вложенный цикл, начиная с текущего элемента c шагом K будет сдвигать элемент, пока не вернемся в элемент, с которого начали. Во вложенном цикле будет увеличивать счетчик преобразованных элементов.
Выходим из основного цикла, когда счетчик преобразованных элементов станет равным кол-ву исходных элементов.

Детали смотрите в реализации.