/*
法1:每次將數組向右移動壹位,移動k次
時間復雜度:O(k*n)?
空間復雜度:O(1)?
*/?
void?rightShift1(int?a[],?int?n,?int?k)
{
k=k%n;? while(k--) {? int?t=a[n-1]; for(int?i=n-1;i>0;i--)a[i]=a[i-1];
a[0]=t; }}
/*
法2:借助壹個輔助數組?
時間復雜度:O(n)?
空間復雜度:O(n)?
*/
void?rightShift2(int?a[],?int?n,?int?k)
{
int?b[n];?//這種初始化不規範 k=k%n; for(int?i=0;i<k;i++) b[i]=a[n-k+i]; for(int?i=0;i<n-k;i++) b[k+i]=a[i]; for(int?i=0;i<n;i++) a[i]=b[i];}
//反轉?
void?reverse(int?a[],?int?sta,?int?end)?//左開右閉區間?[sta,end)
{
end-=1;? while(sta<end) { int?t=a[sta]; a[sta]=a[end]; a[end]=t; sta++; end--; }?}?
/*
法3:巧妙利用反轉?Orz
時間復雜度:O(n)?
空間復雜度:O(1)?
*/
void?rightShift3(int?a[],?int?n,?int?k)
{
k=k%n; reverse(a,?0,?n-k); reverse(a,?n-k,?n); reverse(a,?0?,?n);}