LeetCode原文：http://articles.leetcode.com/2010/04/rotating-array-in-place.html 

Rotate a one-dimensional array of n elements to the right by k steps. 
For instance, with n=7 and k=3, the array {a, b, c, d, e, f, g} is rotated to {e, f, g, a, b, c, d}.

在前面的博文（Searching an Element in a Rotated Sorted Array）中，我们讨论了怎样从一个旋转过的数组中找出特定的元素。你可能会问，我们怎样旋转一个数组？

一个比较直接的方式是分配一个大小为n的数组，然后以原数组的下标k为起点将元素拷贝至新数组，然后再拷贝回旧数组。这种方式很不高效，因为：

该方法需要额外的空间保存临时数组（O(n)空间）

该方法需要来回拷贝数组元素，总计2 * n次拷贝操作

那么问题来了，我们能否以一种更加高效的方式实现数组的就地旋转？

答案当然是可以。这个问题经常在面试中出现，《编程珠玑》中有对该问题的深度讨论，这本书是计算机科学领域的必读书目之一。

解决问题的技巧就是执行三次逆置操作。对整个数组执行一次，从0到k-1执行一次，然后从k到n-1执行一次。非常神奇，这就可以得到旋转后的正确数组，不需要任何额外的空间。（当然，你可能需要一个临时变量来执行交换操作；实际上也可以不用临时变量)

void reverse_string(char* str, int left, int right) {
  char* p1 = str + left;
  char* p2 = str + right;
  while (p1 < p2) {
    char temp = *p1;
    *p1 = *p2;
    *p2 = temp;
    p1++;
    p2--;
  }
}
 
void rotate(char* str, int k) {
  int n = strlen(str);
  reverse_string(str, 0, n-1);
  reverse_string(str, 0, k-1);
  reverse_string(str, k, n-1);
}

 

本文链接：http://bookshadow.com/weblog/2015/02/26/rotating-array-in-place/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码