c++ - 顺时针和逆时针旋转数组的有效方法

Question

我在 C++ 中顺时针和逆时针旋转数组或 vector 。就时间复杂度而言，哪种方法最有效？我使用了 rotate() 函数，但我想知道有没有比这更快的方法？

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
   vector<int> v;
   for(int i=0;i<5;i++)
      v.push_back(i);
   int d=2;
   rotate(v.begin(),v.begin()+d,v.end());
   return 0;
}

Answer 1

rotate() 是一个线性时间函数，这是您能做的最好的。

不过，如果需要做多次旋转，可以累加。

例如:4的旋转和5的旋转与9的单次旋转相同。

或者事实上，在某些应用程序中，您甚至可能不想实际旋转。

比如，如果你想按“d”旋转。你可以只创建一个函数，在请求 v[i] 时返回 v[(i+d)%v.size()]。这是恒定时间的解决方案。但正如我所说，这是特定于应用程序的。