通过数组逆置进行循环移位

通过数组逆置进行循环移位

2018-09-09

---

Question
设计算法将数组a[n]循环左移k位,并要求时间复杂度O(n),只能用一个元素的辅助空间。
循环移位前：
1 2 3 4 5 6 7 8 9 10
循环移动k位：
k=3
循环移位后：
4 5 6 7 8 9 10 1 2 3

Answer

void RRotate(int a[],int k,int n)
{
    Reverse(a,0,k-1);
    Reverse(a,k,n-1);
    Reverse(a,0,n-1);
}
//逆置
void Reverse(int a[],int start,int end) 
{
    int i=0;
    int temp;
    for( i=0 ; i<=(end-start)/2 ; i++)
    {
        temp = a[start+i];
        a[start+i] = a[end-i];
        a[end-i] = temp;
    }
}

Main Idea
先将前k位逆置，再将后length-k位逆置，最后再将整个数组逆置
0.0即得到结果。(:зゝ∠)