题目：设计一个算法，把一个含有N个元素的数组循环右移K位，要求时间复杂度为O（N），且只允许使用两个附加变量。
这个问题，我在面试中也问过，几乎所有的candidates都能给出解法一，至于解法二，并没有新意，读过STL源代码的人都知道：
STL里面的rotate函数<algorithm>，就是用这种方法实现的
template<class _BidIt> inline
void _Rotate(_BidIt _First, _BidIt _Mid, _BidIt _Last, bidirectional_iterator_tag)
{
std::reverse(_First, _Mid);
std::reverse(_Mid, _Last);
std::reverse(_First, _Last);
}
但是，STL只是在一个数组里面移位，所移动的长度不会超过数组的大小。如果一个长度是3的数组循环右移1000000位，也就是 K >> N的时候
RightShift(int* arr, int N, int k)
{
K %= N ; //很简单但是不同反响的一句
..........
}
[版权声明]BSD爱好者乐园站内文章，如来源不是互联网，则均系原创或翻译之作，可随意转载，或以此为基础进行演译，但务必以链接形式注明原始出处和作者信息，否则属于侵权行为。另对本站转载他处文章，俱有说明，如有侵权请联系本人，本人将会在第一时间删除侵权文章。
TAG: 编程之美 读书笔记