编程之美2.17 数组循环移位

本站寻求有缘人接手，详细了解请联系站长QQ1493399855

      这是一个很经典的题目，题目的大概意思是这样的：

      有一个存储字符串的数组，需要按照要求循环移动数组中的字符，例如，数组中存储字符 abcd1234，循环右移4位，之后，会得到这样一个字符数组 1234abcd，当然，左移也是同样的解法

      想想这个问题不是很难，顺序依次移动就可以了，这样做的话，时间复杂度是O(n2)量级的，那么，有没有更快的方法呢？

      首先，我们需要对数组的前四位进行翻转（前面的例子），得到dcba1234，之后，我们再对后4位进行翻转，得到dcba4321，最后，我们再对整体进行翻转，得到：1234abcd，就是这样，解决了这个问题，由于翻转一个字符串需要的时间复杂度是O（n），所以，该算法的时间复杂度是O（n）量级的。

      下面给出解决方法：      

template <typename T>
void DutCircleShift(T* A, int size, int k)
{k %= size;DutReverse<T>(A, 0, size - k - 1);DutReverse<T>(A, size - k, size - 1);DutReverse<T>(A, 0, size - 1);
}

/*翻转函数*/
template <typename T>
void DutReverse(T* A, int low, int high)
{for (; low < high; ++low, --high){T temp = A[low];A[low] = A[high];A[high] = temp;}return;
}

      代码中的第一句代表如果输入的那个数（即循环移动的数字）大于数组的长度，那么，就对这个数按照数组长度取余。