Thursday, March 10, 2016

Rotate Array

from here

1. 问题描述

将一个具有n个元素的向量,向左旋转i个位置。
例如,具有8个元素的向量abcdefgh,向左旋转3个元素的结果是defghabc。



第二种解法,这种解法来自于C++ STL的rotate调用的源码,代码如下:
template <class ForwardIterator>  
  void rotate ( ForwardIterator first, ForwardIterator  middle,     
                 ForwardIterator last )     
{   
  ForwardIterator next = middle;    
  while (first!=next)      
  {     
     swap (*first++,*next++);   
     if (next==last) next=middle; //注意,这两个if不能交换位置  
      else if (first == middle) middle=next;      
  }  
}  
上面的伪代码可能不太好理解,我们来分析一下。
假设数组有N个元素,旋转i位,且(N>i),我们首先考虑i < N-i的情况,我们可以把数组分成三部分,分别是 ab1 b2,其中,a的长度等于b1的长度,然后算法执行一轮以后,就得到 b1ab2,剩下要做的事情就是交换ab2的顺序,且中点应该在ab2交接的地方,所以有middle=next,假设此时b2的长度小于a,则将划分为a1a2b2,然后再执行一次while循环,整个数组就变成了b1b2a2a1,现在是要交换a2和a1的顺序即可。
交换a2和a1的顺序其实和交换a和b的顺序是一样的,只是元素更少了。
完整的代码如下所示:
#include <stdio.h>
#include <string.h>

void swap(char *p, char *q)
{
    if ( p == NULL || q == NULL) return;

    char temp = *p;
    *p = *q;
    *q = temp;
}


void rotate(char* first, char* middle, char* last)
{
    char *next = middle;
    while( first != next)
    {
        swap( first++, next++);
        if (next == last){ next = middle;}
        else if ( first == middle ) { middle = next;}
    }
    return;
}


int main(int argc, char* argv[])
{

   char str[] = "abcdefgh";
   int n = strlen(str);
   int i = 3;
   rotate( str, str + i, str + n);
   printf("%s\n", str);
   return 0;
}

No comments:

Post a Comment