[趣味]How to rotate an array with O(1) extra space?

zclll

2021 年 12 月 24 日

3032 次浏览

1 条评论

1456字数

算法

rotate(旋转)是指的如下一种操作:

$$
arr=[1,2,3,4,5]

$$
arr^{'}=rotate(arr, dis=2)

则

$$
arr^{'}=[4,5,1,2,3]

朴素的rotate需要$O(n)$的额外空间, 以下介绍两种只需要$O(1)$额外空间的做法:

## 做法1——reverse

观察到rotate之后的数组相较于之前的, 是以某位置为分割, 后面的元素移动到了前面, 前面的移动到了后面, 内部顺序不变.

因为reverse(翻转)操作只需要$O(1)$额外空间, 且能够实现这个目的, 我们可以先翻转$arr$, 得到

$$
[5,4,3,2,1]

发现相对位置关系已经达成, 只要再调整两部分内部顺序即可, 这可以通过$reverse([5,4])$和$reverse([3,2,1])$实现, 从而得到

$$
[4,5,1,2,3]

### 代码

```cpp
void rotate_by_reverse(vector<int> &arr, int k)
{
	k %= arr.size();
	reverse(arr.begin(), arr.end());
	reverse(arr.begin(), arr.begin()+k);
	reverse(arr.begin()+k, arr.end());
}
```

## 做法2——模等价关系

让我们考察rotate的本质, 例如

$$
b = rotate(a, dis = k), \space a.len = L

我们规定下标从$0$开始, 对此有

$$
b_i = a_{(i-k+L)\%k}

由这个定义我们可以知道, 移位前后的点之间可以连一条有向边, 那么整个序列将会成环, 环的个数恰好为$\gcd(L,k)$.

例如

$$
a = [1,2,3,4,5,6,7,8,9, 10],\space k=3

有$gcd(10,3)=1$, 因此遍历一次环, 做$k=1$的rotate即可. 由于$k=1$时rotate可以由递推简单实现, 因此达成了我们的要求.

如

$$
a=[1,2,3,4,5,6], \space k=4

就会有$\gcd(4,6)=2$个环. 那么我们就需要对这两个环都进行rotate.

环的起点显然是$[0, \gcd(L,k)-1]$, 这可以使用反证法简单证明.

### 代码

```cpp
void rotate_by_modulo(vector<int> &arr, int k)
{
	k %= arr.size();
	for (int i = 0; i < __gcd(k, (int)arr.size()); i++)
	{
		int t = arr[i];
		for (int j = i + k; j != i; j = (j + k) % arr.size())
			swap(arr[j], t);
		arr[i] = t;
	}
}
```

这一种做法时间复杂度显然是更劣的, 仅作为一种思维开拓的练习而已.