为什么我的算法旋转数组右k次没有额外的数组运行在O(n)只适用于小数组，而不是大数组?

Question

我正在尝试解决和尚和旋转在HackerEarth(这里)上给出的问题，我知道市场上的其他算法可以为我做这项工作，但我试图制作一种新的高效算法，用于将数组元素向右旋转k倍，而不使用另一个数组，也不使用任何自定义库函数并尝试在中运行它O(n)。因此，我想出了我的解决方案我从数组的第一个元素开始使用temp变量来存储第一个元素然后交换temp元素在旋转后会出现在数组索引处，然后在旋转后再次与下一个位置交换特定元素，以此类推……当temp变量等于给定数组的起始元素。

注意:我假设所有的元素都是不同的

但问题是它在我的本地系统中为我工作，并且也通过了HackerEarth网站上提到的测试用例，但我无法通过那里的其他私有测试用例。

---

下面是我的代码供您参考:

#include <bits/stdc++.h> 
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
int main() {
ll t, temp;
cin >> t;    //inputing test cases
while(t--){
vl arr;
ll i,n,k;
cin>>n>>k;
for(i=0;i<n;i++){    //inputing array
cin>>temp;
arr.push_back(temp);
}

/*Main Algo*/
ll temp1 = arr[0];
temp = arr[0];
while(1){
i = (i+k)%(n);
swap(arr[i], temp);
//cout<<"temp: "<<temp<< endl;
if(temp == temp1)break;
}
//Printing Rotated Array
for(i=0;i<n;i++){
cout<<arr[i]<<" ";
}
}
return 0;
}

测试用例的示例:

1 
5 2
1 2 3 4 5

我输出:

4 5 1 2 3 

Answer 1

为什么我的自定义算法[…]只适用于小数组，而不适用于大数组?

因为不能保证使用重复的i = (i+k)%n增量访问所有元素。

更具体地说，这只会在n和k没有公约数(除了1)时起作用。

例如，如果n= 4且k= 2，则永远不会访问数组的奇数下标。