【题目】有一个整数数组，现要求实现这个整数数组的循环右移。如：1，2，3，4，5 则循
环右移两位后结果是：4，5，1，2，3。
方法一：（最最容易想到的办法）
void RightCircleShift_00(int buffer[],int shift)
{
int i,j,tt;
for(i=0;i<shift;i++)
{
tt = buffer[ARRSIZE-1];
for(j=ARRSIZE-1;j>0;j--)
buffer[j] = buffer[j-1];
buffer[0] = tt;
}
}
这个办法是用两个循环来控制，内循环每次向右移动一位，外循环则用来限制移动的位数。
算法需要执行 ARRSIZE * ShiftValue次，时间复杂度是O( N2 )。
方法二：（由方法一得到的递归程序）
void RightCircleShift_01(int buffer[],int shift)
{
int *p,tt;
tt = *(buffer+ARRSIZE-1);
for(p = buffer+ARRSIZE-1;p > buffer;p--)
*p = *(p-1);
*buffer = tt;
shift--;
if(shift > 0)
RightCircleShift_00(buffer,shift);
}
这个程序跟方法一类似，区别就是它是用递归来实现的。同样需要执行ARRSIZE *
ShiftValue次，时间复杂度也是O( N2 )。
方法三：
void RightCircleShift_02(int buffer[],int shift)
{
int *title,*r,*p;
if(shift == 0)
return;
shift = shift % ARRSIZE;
title = (int *)malloc(sizeof(int)*shift);
if( title == NULL )
return;
r = buffer + (ARRSIZE - shift);
memcpy(title, r, shift * sizeof(int));
p = buffer + shift;
memmove(p, buffer, (ARRSIZE - shift) * sizeof(int));
memcpy(buffer, title, shift * sizeof(int));
free(title);
}
这个算法需要移动位数大小的临时辅助空间。如需移动两位，则申请两个的空间，然后把从
右边起的两个元素拷贝的临时辅助空间，然后前面的元素向后移动两位，最后再把临时空间
里面的两个元素拷贝到前面的两位即可完成循环右移。需要执行 ARRSIZE次，时间复杂度是
O( N )。
方法四：从内存模型上出发。
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
void Rotate(int* beg, int* newBeg, int* end)
{
int numElems = end - newBeg;
int* temp = (int*)malloc(sizeof(int)*(end - newBeg));
memcpy(temp, newBeg, (end - newBeg)*sizeof(int));
memmove(beg + numElems, beg, (newBeg - beg)*sizeof(int));
memcpy(beg, temp, (end - newBeg)*sizeof(int));
free(temp);
}
int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for(int i = 0; i < 10; ++i)
{
Rotate(a, a + 1, a + 10);
for(int j = 0; j < 10; ++j)
printf("%d ", a[j]);
printf("\n");
}
}
方法五：先把N个字符逆序，再把前M个字符逆序，最后再把这N － M个字符逆序，即得到最
终结果。
代码实现如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名称：StringShift.c
* 简要描述：字符串循环左移
*
* 当前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 开发环境：Windows XP Sp2 + VC6.0
* 个人博客：http://raincatss.cublog.cn/
******************************************************************/
#include <string.h>
#include <assert.h>
static void Swap(char *p, char *q);
static void Reverse(char *str, int i, int n);
void String_Shift_Reverse(char *str, int n)
{
int len;
assert(NULL != str);
len = strlen(str);
if (n <=0 || n >= len) {
return;
}
Reverse(str, 0, n - 1);
Reverse(str, n, len - 1);
Reverse(str, 0, len - 1);
}
static void Swap(char *p, char *q)
{
char tmp;
tmp = *p;
*p = *q;
*q = tmp;
}
static void Reverse(char *str, int i, int n)
{
int l, r;
for (l = i, r = n; l < r; l++, r--) {
Swap(&str[l], &str[r]);
}
}
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
rotate(a, a + 10 - 4, a + 10);
for(int i = 0; i < 10; ++i)
cout << a[i] << ' ';
}
方法六：这是我给出的方法，我认为是最最好的一种方法，简直了，无语了。。。。
不过网上也有人想到了，呵呵。
但是这个方法要求被处理的数组长度或位移的位数中至少有一个奇数。
#include <stdio.h>
void move(int * ptr, int n, int m)
{
if(m<=0)
return;
if(!(n%2 || m%2))
{
move(ptr,n,m-1);
move(ptr,n,1);
return;
}
int pos=0;
int i=0;
while(++i<n)
{
pos=(pos+m)%n;
int tmp=*ptr;
*ptr=*(ptr+pos);
*(ptr+pos)=tmp;
}
}
void main()
{
int a[]={1,2,3,4,5,6,7,8,9,10};
move(a,10,7);
for(int i=0;i<10;i++)
printf("%d ",a[i]);
}
该方法对位移数m没有任何要求，只要不为负数就可以。
此外，交换两个数据可以不用任何的临时空间的，优化后的代码如下：
void move(int * ptr, int n, int m)
{
if(m<=0)
return;
if(!(n%2 || m%2))
{
move(ptr,n,m-1);
move(ptr,n,1);
return;
}
int pos=0;
int i=0;
while(++i<n)
{
pos=(pos+m)%n;
*ptr^=*(ptr+pos);
*(ptr+pos)^=*ptr;
*ptr^=*(ptr+pos);
}
}
再优化：
void move(int * ptr, int n, int m)
{
if(m<=0)
return;
if(!(n%2 || m%2))
{
move(ptr,n,m-1);
move(ptr,n,1);
return;
}
int pos=0;
int i=0;
while(++i<n)
{
pos=(pos+m)%n;
*ptr^=*(ptr+pos)^=*ptr^=*(ptr+pos);
}
}
再用逗号表达式优化：
void move(int * ptr, int n, int m)
{
if(m<=0)
return;
if(!(n%2 || m%2))
{
move(ptr,n,m-1);
move(ptr,n,1);
return;
}
int pos=0;
int i=0;
while(pos=(pos+m)%n,++i<n)
*ptr^=*(ptr+pos)^=*ptr^=*(ptr+pos);
}
最后再优化判断是否为偶数的运算：
void move(int * ptr, int n, int m)
{
if(m<=0)
return;
if(!( n&1 || m&1 ))
{
move(ptr,n,m-1);
move(ptr,n,1);
return;
}
int pos=0;
int i=0;
while(pos=(pos+m)%n,++i<n)
*ptr^=*(ptr+pos)^=*ptr^=*(ptr+pos);
}
还有别人给出的一些方法：
分析：
最容易想到的方法有两种：
申请一个3个字节的空间，把“ABC”复制进去，然后把剩下的字符从左到右依次移到相应的位置，最后把“ABC”再复制到最后，释放空间，算法结束。这样时间复杂度为O（N），空间复杂度为O（M）。
只用一个字节的辅助空间，每次把字符串循环左移一位，共移M次。这样时间复杂度为O（M·N），空间复杂度为O（1）。
以上两种方法虽然简单，但时间（或空间）复杂度令人不尽满意，有没有时间复杂度为O（N），空间复杂度为O（1）的算法呢？下面我们来研究一下。
方案一
设字符串长度为N，临时变量为t，算法步骤如下：
设i = 0
j = i，保存s[j]到t
把s[(j + N) % M]向前移N位到最终位置s[j % M]
j += N
如果j % M != i，则转3；否则下一步
i++
如果i < gcd(M, N)，则转2；否则移动完毕，算法结束
实现代码如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名称：StringShift.c
* 简要描述：字符串循环左移
*
* 当前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 开发环境：Windows XP Sp2 + VC6.0
* 个人博客：http://raincatss.cublog.cn/
******************************************************************/
#include <stdio.h>
#include <string.h>
#include <assert.h>
static int gcd(int m, int n);
void StringShift(char *str, int n)
{
int i, j, len;
char tmp;
assert(NULL != str);
len = strlen(str);
if (n <= 0 || n >= len) {
return;
}
for (i = 0; i < gcd(len, n); i++) {
j = i;
tmp = str[j];
do {
str[j] = str[(j + n) % len];
j = (j + n) % len;
} while (j != i);
str[(j + len - n) % len] = tmp;
}
}
static int gcd(int m, int n)
{
int tmp;
while (n != 0) {
tmp = m % n;
m = n;
n = tmp;
}
return m;
}
在do{}while()循环中，如果k每次加n后不与len取模，可以发现k - i最后等于M、N的最小公倍数，这样保证在循环过程中无重复下标（为什么？请自己想一下）。之所以让for()循环做gcd(M, N)次，是因为每次do{}while()循环做M * N / （N * gcd(M, N)) = M / gcd(M, N)次，for()循环做gcd(M, N)次正好可以保证移动M次，即所有元素移动一次。（如果谁有此法的精确且清楚的数学证明，请发Email:raincatss#gmail.com）
方案二
把原字符串分成三部分ABlBr（Br与A长度相同），循环左移后为BlBrA。可以先把A与Br互换位置，变为BrBlA，然后再把Br与Bl互换，由此可以递归求解。
递归实现代码如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名称：StringShift.c
* 简要描述：字符串循环左移
*
* 当前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 开发环境：Windows XP Sp2 + VC6.0
* 个人博客：http://raincatss.cublog.cn/
******************************************************************/
#include <stdio.h>
#include <assert.h>
static void Swap(char *p, char *q);
void StringShift(char *str, int len, int n)
{
int i;
assert(NULL != str);
if (len <= 0 || n <= 0 || n >= len) {
return;
}
if (n < len - n) {
for (i=0; i<n; i++) {
Swap(&str[i], &str[len - n + i]);
}
StringShift(str, len - n, n);
} else if (n > len - n) {
for (i=len-1; i>n-1; i--) {
Swap(&str[i], &str[i - n]);
}
StringShift(str + len - n, n, n + n - len);
} else {
for (i=0; i<n; i++) {
Swap(&str[i], &str[n + i]);
}
}
}
static void Swap(char *p, char *q)
{
char tmp = *p;
*p = *q;
*q = tmp;
}
为提高效率，可以把递归转换为迭代，实现代码如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名称：StringShift.c
* 简要描述：字符串循环左移
*
* 当前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 开发环境：Windows XP Sp2 + VC6.0
* 个人博客：http://raincatss.cublog.cn/
******************************************************************/
#include <stdio.h>
#include <assert.h>
static void Swap(char *p, char *q);
void StringShift(char *str, int len, int n)
{
int i, tmp;
char *s = str;
assert(NULL != str);
if (len <= 0 || n <= 0 || n >= len) {
return;
}
while (n != len - n) {
if (n < len - n) {
for (i=0; i<n; i++) {
Swap(&s[i], &s[len - n + i]);
}
len -=n;
} else {
for (i=len-1; i>n-1; i--) {
Swap(&s[i], &s[i - n]);
}
s += len - n;
tmp = n;
n = n + n - len;
len = tmp;
}
}
for (i=0; i<n; i++) {
Swap(&s[i], &s[n + i]);
}
}
static void Swap(char *p, char *q)
{
char tmp = *p;
*p = *q;
*q = tmp;
}