向量旋转

定义

向量的旋转是指将向量中每一个元素循环左移或者右移。左移和右移一定程度上是等价的，本文均以右移为例。

有两种表示方式：

rotate: vector.begin(), vector.end(), steps

rotate: vector.begin(), iterator_middle, vector.end()

其中，第一种意义与定义相同。

第二种是指旋转之后以 iterator_middle 为新的起始元素。即：

Before rotate:
begin, begin + 1, ..., middle, middle + 1, ..., end - 1

After rotate:
middle, middle + 1, ..., end - 1, begin, begin + 1, ..., middle - 1

使用

在 C++ 中使用 std::rotate(begin, middle, end) 来旋转向量以及其他有前向迭代器的容器。

如果需要旋转无迭代器的容器中的元素，请参考实现中的方法三。

实现

方法一 朴素算法

朴素实现是开一个等大的向量，然后遍历拷贝。消耗空间较大，故略过。

方法二 STL标准实现

STL 的标准实现为一个时间复杂度 $O(n)$，空间复杂度 $O(1)$ 的算法。

此方法先将 (begin, middle) 和 (middle, end) 中较短的部分交换，然后交换更长者的剩余部分。

template<class Iterator>
void rotate(Iterator first, Iterator medium, Iterator end) {
    Iterator next = middle;
    while (first != next)
    {
        swap (first++, next++);
        if (next==end) next = middle;
        else if (first==middle) middle = next;
    }
}

方法三 简单实现

设 $a = [begin, middle), b = [middle, end)$，对于初始向量 $ab$，要得到的结果向量为 $ba$。而

$$ ba = (a^{-1}b^{-1})^{-1} $$

其中 $^{-1}$ 指对序列取反。所以这个简单算法如下：

template<class Iterator>
void rotate(Iterator first, Iterator medium, Iterator end) {
    reverse(first, medium);
    reverse(medium, end);
    reverse(first, end);
}

此方法适用于需要手搓轮子的情况。比如二维 vector 矩阵需要按列旋转时。