编程之美2.17之数组循环移位

本文主要是介绍编程之美2.17之数组循环移位，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：设计一个算法，把一个含有N个元素的数组循环右移K位，要求算法的时间复杂度位$O(Log_2N)$,且只允许使用两个附加变量。
什么意思呢，就是说如果输入序列为：abcd1234，右移2位即变为34abcd12。唯一的要求就是使用两个附加变量。
其实这道题编程珠玑上面也出现过，书中给出的一种符合题意的解法是巧妙地进行翻转。以把abcd1234右移4位为例：

第一步：翻转1234，abcd1234———->abcd4321

第二步：翻转abcd，abcd4321———->dcba4321

第三步：整体翻转，dcba4321———->1234abcd

如果是代码实现，那也是很简单的了。我的一个实现如下：

#include <iostream>
#include <string>
using namespace std;
void reverse(string& str,int begin,int end){for(;begin<end;begin++,end--){char temp=str[begin];str[begin]=str[end];str[end]=temp;}
}
void rightShift(string &str,int len,int K){K%=len;reverse(str,0,len-K-1);reverse(str,len-K,len-1);reverse(str,0,len-1);
}
int main(int argc,char **argv){string str="MarkLiang19941028";int k;cout<<"Enter K:"<<endl;cin>>k;cout<<"Before Reverse:\n"<<str<<endl;rightShift(str,str.size(),k);cout<<"After Reverse:\n"<<str<<endl;return 0;
}

参考书籍：编程之美，编程书籍

这篇关于编程之美2.17之数组循环移位的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---