【題目】有一個整數(shù)數(shù)組，現(xiàn)要求實(shí)現(xiàn)這個整數(shù)數(shù)組的循環(huán)右移。如：1，2，3，4，5 則循
環(huán)右移兩位后結(jié)果是：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;
}
}
這個辦法是用兩個循環(huán)來控制，內(nèi)循環(huán)每次向右移動一位，外循環(huán)則用來限制移動的位數(shù)。
算法需要執(zhí)行 ARRSIZE * ShiftValue次，時(shí)間復(fù)雜度是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);
}
這個程序跟方法一類似，區(qū)別就是它是用遞歸來實(shí)現(xiàn)的。同樣需要執(zhí)行ARRSIZE *
ShiftValue次，時(shí)間復(fù)雜度也是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);
}
這個算法需要移動位數(shù)大小的臨時(shí)輔助空間。如需移動兩位，則申請兩個的空間，然后把從
右邊起的兩個元素拷貝的臨時(shí)輔助空間，然后前面的元素向后移動兩位，最后再把臨時(shí)空間
里面的兩個元素拷貝到前面的兩位即可完成循環(huán)右移。需要執(zhí)行 ARRSIZE次，時(shí)間復(fù)雜度是
O( N )。
方法四：從內(nèi)存模型上出發(fā)。
#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個字符逆序，即得到最
終結(jié)果。
代碼實(shí)現(xiàn)如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名稱：StringShift.c
* 簡要描述：字符串循環(huán)左移
*
* 當(dāng)前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 開發(fā)環(huán)境：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] << ' ';
}
方法六：這是我給出的方法，我認(rèn)為是最最好的一種方法，簡直了，無語了。。。。
不過網(wǎng)上也有人想到了，呵呵。
但是這個方法要求被處理的數(shù)組長度或位移的位數(shù)中至少有一個奇數(shù)。
#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]);
}
該方法對位移數(shù)m沒有任何要求，只要不為負(fù)數(shù)就可以。
此外，交換兩個數(shù)據(jù)可以不用任何的臨時(shí)空間的，優(yōu)化后的代碼如下：
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);
}
}
再優(yōu)化：
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);
}
}
再用逗號表達(dá)式優(yōu)化：
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);
}
最后再優(yōu)化判斷是否為偶數(shù)的運(yùn)算：
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個字節(jié)的空間，把“ABC”復(fù)制進(jìn)去，然后把剩下的字符從左到右依次移到相應(yīng)的位置，最后把“ABC”再復(fù)制到最后，釋放空間，算法結(jié)束。這樣時(shí)間復(fù)雜度為O（N），空間復(fù)雜度為O（M）。
只用一個字節(jié)的輔助空間，每次把字符串循環(huán)左移一位，共移M次。這樣時(shí)間復(fù)雜度為O（M·N），空間復(fù)雜度為O（1）。
以上兩種方法雖然簡單，但時(shí)間（或空間）復(fù)雜度令人不盡滿意，有沒有時(shí)間復(fù)雜度為O（N），空間復(fù)雜度為O（1）的算法呢？下面我們來研究一下。
方案一
設(shè)字符串長度為N，臨時(shí)變量為t，算法步驟如下：
設(shè)i = 0
j = i，保存s[j]到t
把s[(j + N) % M]向前移N位到最終位置s[j % M]
j += N
如果j % M != i，則轉(zhuǎn)3；否則下一步
i++
如果i < gcd(M, N)，則轉(zhuǎn)2；否則移動完畢，算法結(jié)束
實(shí)現(xiàn)代碼如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名稱：StringShift.c
* 簡要描述：字符串循環(huán)左移
*
* 當(dāng)前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 開發(fā)環(huán)境：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()循環(huán)中，如果k每次加n后不與len取模，可以發(fā)現(xiàn)k - i最后等于M、N的最小公倍數(shù)，這樣保證在循環(huán)過程中無重復(fù)下標(biāo)（為什么？請自己想一下）。之所以讓for()循環(huán)做gcd(M, N)次，是因?yàn)槊看蝑o{}while()循環(huán)做M * N / （N * gcd(M, N)) = M / gcd(M, N)次，for()循環(huán)做gcd(M, N)次正好可以保證移動M次，即所有元素移動一次。（如果誰有此法的精確且清楚的數(shù)學(xué)證明，請發(fā)Email:raincatss#gmail.com）
方案二
把原字符串分成三部分ABlBr（Br與A長度相同），循環(huán)左移后為BlBrA。可以先把A與Br互換位置，變?yōu)锽rBlA，然后再把Br與Bl互換，由此可以遞歸求解。
遞歸實(shí)現(xiàn)代碼如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名稱：StringShift.c
* 簡要描述：字符串循環(huán)左移
*
* 當(dāng)前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 開發(fā)環(huán)境：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;
}
為提高效率，可以把遞歸轉(zhuǎn)換為迭代，實(shí)現(xiàn)代碼如下：
/******************************************************************
* Copyright (c) 2005-2007 CUG-CS
* All rights reserved
*
* 文件名稱：StringShift.c
* 簡要描述：字符串循環(huán)左移
*
* 當(dāng)前版本：1.0
* 作 者：raincatss
* 完成日期：2007-11-18
* 開發(fā)環(huán)境：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;
}