C语言实现数组的就地旋转

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

暂无评论

张贴您的评论