矢量旋转最后的内容到开始

Question

我有一个带有元素的向量我想让它们旋转，基本上我想把最后x个元素推到向量的开头:

1 2 3 4 5 6 7 8 9 
4 5 6 7 8 9 1 2 3 

这是我当前的实现:

#include <iostream>
#include <vector>
int main()
{
    int size = 9;
    std::vector<int> vec(size);
    for(int i = 0; i < size; i++)
    {
        vec[i] = i + 1;
    }
    for(int i = 0; i < size; i++)
    {
        std::cout << vec[i] << ' ';
    }
    std::cout << std::endl;
    int spinCount = 6;
    for(int i = 0; i < spinCount; i++)
    {
        int last = vec[size - 1];
        for(int j = size - 1; j > 0; j--)
        {
            int num = vec[j - 1];
            vec[j] = num;
        }
        vec[0] = last;
    }
    for(int i = 0; i < size; i++)
    {
        std::cout << vec[i] << ' ';
    }
    std::cout << std::endl;
}

但是它在循环中有一个循环，使它成为一个平方复杂度。有没有办法让它更有效率?

Answer 1

std::rotate( begin(vec), begin(vec)+3, end(vec) );

将vec旋转3个位置，使前3个元素现在位于末尾。

Answer 2

与其与为使用std::deque而设计的向量作斗争。它有push_front方法，你可以使用没有手动编码循环

Answer 3

我的答案中的算法与vector的大小一样多。这是一个递归算法。让我用语言向你描述:

首先需要检查currentIndex是否超出vector的边界。如果是，那么对于给定的value，旋转结束。然后，我们必须知道在保存当前旋转的value之后有多少元素需要一个新值，spinCount是要旋转的元素的数量。如果vec仍然有足够的空间进行完整的移位，那么我们在新索引上触发一个新的移位。如果没有足够的空间来换班，那么我们就按需要的量换班。最后，将值保存在currentIndex。

void rotateMyVector(std::vector<int> &vec, int size, int currentIndex, int spinCount, spinIndex, int value) {
    if (currentIndex >= size) {
        return;
    }
    int amount = size - currentIndex + spinIndex - spinCount;
    if (amount >= spinCount) {
        rotateMyVector(vec, size, currentIndex + spinCount, spinIndex, vec[currentIndex]);
    } else {
        vec[currentIndex + amount] = vec[currentIndex];
    }
    vec[currentIndex] = value;
}

然后我们必须在代码中的适当位置调用该函数:

for (int index = size - spinCount; index < size; index++) {
    rotateMyVector(vec, size, index - (size - spinCount), index - (size - spinCount), vec[index]);
}

注意，这个算法没有经过测试，如果我在任何地方打错了，请告诉我。