c++ - 逆时针旋转阵列，运行时间问题

Question

在这个问题中，我必须将数组中的数据逆时针旋转 d 个数字。但运行时间比获得提交资格所需的时间要长。谁能帮助我如何优化代码以在更短的时间内运行它？谢谢!

代码如下:

int main() {
int test_cases,size,d;
std::cin>>test_cases;
while(test_cases!=0){
std::cin>>size>>d;
int ar[size];
for(int i=0;i<size;i++){
    std::cin>>ar[i];
}
while(d!=0){
    int x = ar[0];
    for(int i=1;i<size;i++){
        ar[i-1]=ar[i];
    }
    ar[size-1]=x;
    d--;
}
for(int i=0;i<size;i++){
    std::cout<<ar[i]<<" ";
}
test_cases--;
cout<<endl;
}}

Answer 1

您应该按照评论中的建议移动每个元素一次。找出一种算法来做到这一点并不难。但是，为什么要重新发明轮子呢？

您可以简单地使用std::rotate。我假设逆时针意味着向左，并且数组从左侧开始并在右侧结束:)。

std::vector<int> v {1,2,3};
size_t dist = 4; // rotate 4 to the left
std::rotate(v.begin(), v.begin() + dist % v.size(), v.end());

如果你真的坚持重新发明轮子，我猜有很多可能的算法。下面的示例从索引 idx = 0 开始，并存储索引 idx_moved = idx + dist 处的值，其中 dist 是旋转距离。然后我们对 idx = idx_moved 进行同样的操作，并重复 N 次，其中 N 是数组的大小。我在这里使用了 std::vector ，但这并没有改变算法。

std::vector<int> v {1,2,3,4,5};
size_t dist = 3; // distance to move to the left

size_t idx = 0;
int tmp = v[0]; // store the initial value

for (size_t it = 0; it < v.size(); ++it)
{
    size_t idx_moved = (idx + dist) % v.size();
    v[idx] = v[idx_moved];
    idx = idx_moved;
}
v[dist * (v.size() -1 ) % v.size()] = tmp; // store the initial value back