字符串循环移动-高效优雅算法

命题:给定一个字符串S[0…N-1],要求把S的前k个字符移动到S的尾部,如把字符串“abcdef”前面的2个字符‘a’、‘b’移动到字符串的尾部,得到新字符串“cdefab”:即字符串循环左移k。

算法要求: 时间复杂度为 O(n),空间复杂度为 O(1)。


算法思考

可以采取的方法有:

直接来个嵌套循环移动,但是时间复杂度不满足,空间复杂度满足。不可取

三次拷贝,利用第三方空间。方便,时间复杂度满足,空间复杂度不满足。不可取

高效优雅的算法:一个离散数学中的式子:(X’Y’)’=YX

多说一句,之前学离散数学觉得只是学逻辑的,感觉在计算机中没多大关系,现在才知道,在算法上,利用离散数学的逻辑公式可以得到非常高效优雅的算法


算法演进

可能看到那个式子还是没有什么思路,那就是知识转化欠缺,但是通过多种练习,就可以很好地利用离散数学中的公式获得高效的算法。

演进:

 (X’Y’)’=YX

 如:abcdef

 X=ab X’=ba

 Y=cdef Y’=fedc

 (X’Y’)’=(bafedc)’=cdefab

 时间复杂度O(N),空间复杂度O(1)


java代码实现

	/**反转。把字符数组从from位置到to位置的数反转*/
	static void revertStr(char[] str, int from, int to){
		if(to - from < 1){
			return;
		}
		for(int i = from; i < (to + from + 1)/2;i++){
			swapChar(str,i,to -(i - from));
		}
	}
	
	static void swapChar(char[] s, int i, int j) {
		char temp = s[i];
		s[i] = s[j];
		s[j] = temp;
	}
	
	/**字符数组str中moveStrHead位置到moveStrEnd位置的字符向右循环移动moveLength位*/
	static void circleLeftMove(char[] str, int moveStrHead, int moveStrEnd, int moveLength){
		revertStr(str, moveStrHead, moveStrEnd);
		revertStr(str, moveStrEnd+1, moveStrEnd + moveLength);
		revertStr(str, moveStrHead, moveStrEnd + moveLength);
	}

测试代码:

	public static void main(String[] args) {
		String test = "123456789";
		char[] charArray = test.toCharArray();
		circleLeftMove(charArray, 0, 2, 2);
		System.out.println(charArray);
	}

输出结果:

451236789


时间复杂度与空间复杂度分析

时间复杂度是:别看调用了三次revertStr()方法,实际上,他们是线性的,所以时间复杂度是O(n)

空间复杂度:明显是O(1)


若要实现其他移动方式,那么对代码稍加改动即可


若有更高效的算法,请留言告知,再次感谢

相关文章
相关标签/搜索