编程之美2.17 数组循环移位

问题描述：

设计一个算法，把一个含有N元素的数组循环左移或者右移K位。

解决方法：

1. 暴力解法------O(KN)

2. 颠倒位置------O(N)

具体思路和代码：

1. 暴力解法------O(KN)

思路：循环K次，每次移动一位

代码：

 1 //右移
 2 void s1(int A[], int n, int k)
 3 {
 4     k = k % n;
 5     for(int i = 0; i < k; i++)
 6     {
 7         int t = A[n-1];
 8         for(int j = n-1; j > 0; j--)
 9         {
10             A[j] = A[j-1];
11         }
12         A[0] = t;
13     }
14 }

 1 //左移
 2 void s3(int A[], int n, int k)
 3 {
 4     k = k % n;
 5     for(int i = 0; i < k; i++)
 6     {
 7         int t = A[0];
 8         for(int j = 1; j < n; j++)
 9         {
10             A[j-1] = A[j];
11         }
12         A[n-1] = t;
13     }
14 }

2. 颠倒位置------O(N)

思路：

例如：1 2 3 4 5 6 7 8 右移2位

3 4 5 6 7 8 1 2

我们分解下：先对换(0, n-k-1) :1 2 3 4 5 6 -> 6 5 4 3 2 1

再对换 (n-k, n-1):7 8 -> 8 7

-> 6 5 4 3 2 1 8 7

　　　　　　整体对换：7 8 1 2 3 4 5 6

代码：

 1 //右移
 2 void reverse(int A[], int l, int r)
 3 {
 4     for(int i = l, j = r; i < j; i++, j--)
 5     {
 6         int t = A[i];
 7         A[i] = A[j];
 8         A[j] = t;
 9     }
10 }
11 
12 void s2(int A[], int n, int k)
13 {
14     reverse(A, 0, n-k-1);
15     reverse(A, n-k, n-1);
16     reverse(A, 0, n-1);
17 }

1 //左移
2 void s4(int A[], int n, int k)
3 {
4     reverse(A, 0, k-1);
5     reverse(A, k, n-1);
6     reverse(A, 0, n-1);
7 }