Разворот массива

Я очень радуюсь, когда задачу получается сильно упростить и свести к какой-то простой последовательности, вместо разработки сложного алгоритма. Еще когда я только учился в универе программированию и не мог решить задачу, я часто выписывал данные на листочек и часами пытался разглядеть какие-то закономерности в их преобразовании, которые приведут меня к искомому решению.

Сегодня рассмотрим как раз такую задачу. У нее стоит средний уровень сложности, хотя на самом деле она очень легкая. И сейчас я вам это докажу 🙂.

Сложность: 🟡 Средняя

ℹ️ Описание

Дан целочисленный массив nums. Поверните массив вправо на k шагов, где k — неотрицательное число.

⚠️ Ограничения

🔹 В массиве может быть от 1 до 10^5 элементов
🔹 В качестве значений могут быть числа в диапазоне от -2^31 до 2^31 - 1
🔹 k в диапазоне от 0 до 10^5

1️⃣ Пример

Входящие данные

nums = [1, 2, 3, 4, 5, 6, 7]
k = 3

Ответ
```
[```5, 6, 7, 1, 2, 3, 4```]```

Объяснение
1. Сдвинуть на 1 шаг вправо: [7,1,2,3,4,5,6]
2. Сдвинуть на 1 шаг вправо: [6,7,1,2,3,4,5]
3. Сдвинуть на 1 шаг вправо: [5,6,7,1,2,3,4]

2️⃣ Пример

Входящие данные

nums = [-1, -100, 3, 99]
k = 2

Ответ

[3, 99, -1, -100]

Объяснение
1. Сдвинуть на 1 шаг вправо: [99,-1,-100,3]
2. Сдвинуть на 1 шаг вправо: [3,99,-1,-100]

✅ Решение

В общем и целом разворот массива k раз в этой задаче подразумевает, что нам нужно сдвинуть все его элементы вправо на одну позицию k раз.

Поначалу в голову придет простой вариант: передвинуть все элементы вправо, а последний перенести на первую позицию и так k раз. Это простое и понятное решение, однако его сложность будет равна O(n * k), что не очень хорошо.

Может показаться, что задачу нельзя решить за линейное время, но это очень просто сделать, если заметить несколько закономерностей.

1. Под поворотом массива на 1 подразумевается смещение всех элементов массива вправо на одну позицию. Исходя из этого, если k будет равно или кратно длине массива, то после всех преобразований все элементы массива пройдут один «круг» и вернутся в исходное состояние.
Это означает, что мы можем отбросить повторяющиеся «круги» и взять только последний.

Для этого нужно найти остаток от деления k на длину массива. В результате мы найдем число count.

Именно на столько позиций надо сместить все элементы вправо.

2. Далее мы можем еще сильнее упростить алгоритм. Если внимательно посмотреть, то можно обнаружить, что для получения искомого результата надо произвести всего три операции:
- полностью развернуть исходный массив относительно центра
- развернуть первые k элементов относительно их центра
- развернуть оставшиеся элементы относительно их центра

Пример

nums = [1,2,3,4,5,6,7]
k = 3

1. Разворачиваем весь массив.

[7,6,5,4,3,2,1]

2. Разворачиваем первые 3 элемента относительно их центра.

[5,6,7,4,3,2,1]

3. Разворачиваем оставшиеся элементы относительно их центра.

[5,6,7,1,2,3,4]

Посмотреть решение в блоге

🅾️ Оценка сложности

n - количество элементов в массиве

По времени

Сложность по времени складывается из нескольких частей:
- O(n/2) — первый разворот массива
- O(k/2) — разворот первого подмассива, где k < n
- O(m/2) — разворот второго подмассива, где m < n

При этом m + k = n, поэтому в сумме сложность равна O(n).

По памяти

Сложность по памяти O(1), так как все изменения производятся in-place.

#medium #arrays