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

Средняя

medium , array , two pointers

13 November 2023

Описание задачи #

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

Ограничения #

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

Примеры #

Входные данные
```
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].
Входные данные
```
nums = [-1, -100, 3, 99]
k = 2
```
Ответ: [3, 99, -1, -100]
1. Сдвинуть на 1 шаг вправо: [99,-1,-100,3].
2. Сдвинуть на 1 шаг вправо: [3,99,-1,-100].

Решение #

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

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

Далее мы можем еще сильнее упростить алгоритм. Если внимательно посмотреть, то можно обнаружить, что для получения результата надо произвести всего три операции:

полностью развернуть исходный массив
развернуть первые k элементов относительно их центра
развернуть оставшиеся элементы относительно их центра

Пример

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

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

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

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

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

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

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

package rotate

func reverse(nums []int, left int, right int) {
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
}

func rotate(nums []int, k int) {
	length := len(nums)
	if length < 2 {
		return
	}

	count := k % length

	reverse(nums, 0, length-1)
	reverse(nums, 0, count-1)
	reverse(nums, count, length-1)
}

export const reverse = (nums: number[], left: number, right: number): void => {
    while (left < right) {
        const tmp = nums[left]
        nums[left] = nums[right]
        nums[right] = tmp
        left++
        right--
    }
}

export const rotate = (nums: number[], k: number): void => {
    const length = nums.length
    if (length < 2) {
        return
    }

    const count = k % length

    reverse(nums, 0, length-1)
    reverse(nums, 0, count-1)
    reverse(nums, count, length-1)
};

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

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

По времени

Сложность по времени складывается из нескольких частей:

O(n/2) — первый разворот массива
O(k/2) — разворот первого подмассива, где k < n
O(m/2) — разворот второго подмассива, где m < n

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

По памяти

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

Оригинал задачи на Leetcode

Algorithmics