循环右移问题

数据结构作业里一道，非常有意思的题。

设计一个算法，将数组An中的元素A[0]至A[n-1]循环右移k位，并要求只用一个元素大小的附加储存，元素移动或交换次数为O(n)。

循环右移的意思就是，如果有一个数组”12345”，循环右移2位，就得到了”45123”，就好像贪吃蛇穿墙一样… 233

其实有个很暴力的解法，就是再额外申请一个数组，来储存移动之后的数组，这样空间和时间复杂度都是O(n)，但是题目要求空间是O(1)的，所以就得换个思路。

我记得TCPL上面有一道二进制数的循环右移的题目，然后翻出来看了一下，题解是直接用位操作，所以可能对于数组实现起来比较复杂，于是就换了一个想法。

解一

这个想法是这样的：

如图:

每次交换都让一个数就位，也就是移动到一个新位置上，并且，把原来这个位置的元素用临时变量存起来，再将原来位置上的元素就位，以此下去，直到所有元素都就位。

但是这样有一个问题，对于移动位数是长度因子的情况，可能出现一趟之后回到原位，无法覆盖所有元素的情况，比如长度为9，移动3位，”1->4->7->1”，从第一位开始移动，又会回到第一位。

这里我从网上看到一个很漂亮的解决思路，用最大公约数，来解决回到原位的情况。

就是说，如果回到了原来的位置，就让指针后移一位，再重复就位的过程。到什么时候结束呢？就是移动位数k和数组长度n的最大公约数，只要走完GCD(k,n)趟，就能够保证所有的元素都就位了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// 循环右移k位移动数组a 长度为n
void move(int a[], int k, int n) {
  k %= n ; // 避免重复移动
  if (!k) return ; 
  for(int i = 0; i < gcd(n,k); i++) { 
    int j = i ;
    int temp = a[j];
    do{
      j = (j+k) % n ; // 移动j到目标位置
      int t = a[j] ; // 保存目标位置旧元素的值
      a[j] = temp ; // 前一个元素就位
      temp = t; // 更新temp的值
    }while(j != i) // 没有回到出发位置
  }
}

解二

这个解法是我在网上看到的，和TCPL上面那道题的解法非常类似，但是相当抽象，比较难想到。

TCPL上面的题是这样的:

编写一个函数rightrot(x,n)，该函数返回将x循环右移n（二进制）位后得到的值。

题解是这样的:

1
2
3
4
5
6
7
8
9
10
11

unsigned rightrot(unsigned x, int n) {
  int wordlength(void); // 求字长函数
  unsigned rbits; 
  if( (n = n % wordlength()) > 0) {
    rbits = ~(~0 << n) & x ; // 构造右边n为全部为0的屏蔽码 取出x右边的n位
    rbits = rbits << (wordlength() - n) ;// 把右边的n位移动到左边
    x = x >> n ; // x 右移 n 位  
    x = x | rbits; // 把刚才右边的n位交给x的左边n位
  }
  return x ;
}

这个解法的核心就是： 一次性把右边要移动的n位取出，然后换到左边

这道数组的题也可以利用这个整体处理思想。

“12345” - > “45123” 其中”123”和”45”的相对位置是没有改变的，利用这一点，我们把数组分为两块，循环右移k位，就是把这两部分进行了一次交换。

然后先整体逆置 “12345”->”54321”

再把右边n-k(3)位逆置 “54321” -> “54123”

再把左边的k(2)位逆置 “54123” - > “45123”

大功告成

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void Reverse(int n, int *a) {
  for (int i = 0; i < n / 2; ++i) {
    int t = a[i];
    a[i] = a[n - i - 1];
    a[n - i - 1] = t;
  }
}
 
void move2(int m, int n, int *a) {
  m %= n;
  if (m == 0) return;
  Reverse(n, a);
  Reverse(m, a);
  Reverse(n - m, a + m);
}

• 数据结构