n元一维向量向左旋转i个位置

问题描述

将n元一维向量向左旋转i个位置。ex:abcdefgh,n=8,i=3,向左旋转后得到的字符串即为defghabc

解决思路分析

思路一

将前i个元素拷贝到一个临时的空间中，将后续的n-i+1个元素向前移动i个位置，再将临时空间中的i个元素连接起来。大概思路就是将向量分为两个部分，借助临时空间交换两个部分的顺序即可。</br> 时间复杂度：O(1)</br> 空间复杂度：O(i)=>O(n)

思路二

对向量进行循环向左移动操作，即将第一个元素移到元素尾端，其它元素一次往前移动，重复上述操作i次即可实现问题要求的旋转</br> 时间复杂度：O(i)=>O(n)</br> 空间复杂度：O(1)

思路三

将向量分为0~i-1与i~n两个部分，将这两个部分分别进行反转，然后对整个向量进行反转，即可达到问题描述的效果。拿上述例子进行说明，分为abc与defgh两个部分，abc反转得到cba，defgh反转得到hgfed，连在一起即为cbahgfed，对cbahgfed进行反转得到defghabc。 分析可知，此思路的核心操作是进行3次反转运算，只要实现一个反转函数即可。</br> 时间复杂度：由反转操作决定</br> 空间复杂度：由反转操作决定

思路三java代码实现

	import junit.framework.TestCase;
	
	
	public class MainTest extends TestCase {
	  //旋转向量函数实现
	  public static String rotate(String source,int i){
	    int n = source.length();
	    StringBuilder head = new StringBuilder(source.substring(0, i)).reverse();
	    StringBuilder end = new StringBuilder(source.substring(i, n)).reverse();
	    return new StringBuilder(head.append(end)).reverse().toString();
	  }
	  
	  public void test(){
	    String example = "abcdefgh";
	    assertEquals("defghabc", rotate(example, 3));
	  }
	}

上述代码中借助了java库中自带的reverse反转函数,性能可能比较差，并且额外消耗了大小为2*n的空间，最好的做法是直接在源source字符串上进行3次反转操作，可以省去额外空间的消耗。

结论

虽然问题实现起来并不难，但当时间、空间复杂度有一定要求的情况下，我们需要精巧的结构和算法来实现，特别是当上述的n值在千万级别的时候，一个低时间、空间复杂度的算法是必须的，而这些精巧的算法需要我们的经验与积累，此篇只是一个开篇，日后会收录总结一些常见的精巧算法。