字符串反转算法
by addy 原创文章,欢迎转载,但希望全文转载,注明本文地址。
本文地址:https://www.iamaddy.net/2017/08/string-reversal-algorithm/
最近在翻阅《编程珠玑》第二版,真的是字字珠玑。在看到第二章的“啊哈,算法”的一道题目,将字符串反转。将一个具有n个元素的一维向量x向左旋转i个位置。例如,将 abcdefg 向左旋转 3 个位置之后得到 defgabc。要求是花费与n成比例的时间以及尽可能少的空间来完成这个操作。看到此题后的第一想法就是临时数组,下面来看下具体代码:
临时数组法
使用js原生splice与concat方法,可减少大量代码:
var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
function swap1 (arr, x) {
return arr.splice(x).concat(arr);
}
console.log(swap1(arr, 4));
不用javascript原生的方法:
var arr2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
function swap2(arr, x) {
var temp = [],
len = arr.length;
for (var i = 0; i < x; i++) {
temp[i] = arr[i];
}
for (var i = x; i < len; i++) {
arr[i - x] = arr[i];
}
for (var i = 0; i < x; i++) {
arr[len - x + i] = temp[i];
}
return arr;
}
console.log(swap2(arr2, 4));
这种方法大多数人都能够想得到,这是最普通的方法,但比较浪费空间。接下来在看一个也比较普通的方法,不使用临时数组。
元素移位
var arr3 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
function swap3(arr, x) {
var temp,
len = arr.length;
for (var i = 0; i < x; i++) {
temp = arr[0];
for (var j = 0; j < len - 1; j++) {
arr[j] = arr[j + 1];
}
arr[j] = temp;
}
return arr;
}
console.log(swap3(arr3, 4));
程序的实现原理也很简单,将第一位元素往后移动,而其他元素向前移动。虽然不浪费空间,但如果x比较大的话,花费的时间成本就比较高了。
机智的反转
下面来看作者给出的一个比较机智的方法,真的是灵光一闪的感觉。原问题可以理解为这样:将原数组看成 ab,需要转换成 ba,先单独对子数组a进行反转得到a’b(a’表示a反转后的结果),同理单独反转b,得到 a’b’,最后将得到的 a’b’ 一起进行一次反转可得 (a’b’)’,而这就是最终结果 ba了。还有一个很形象的图来说明:
你可以用自己的双手照着图反转着试一下,看看结果是不是正确的。下面给出这种反转的代码:
// 反转函数 1234 => 4321
function reverse(arr, start, end) {
var temp,
len = arr.length,
mid = Math.floor((start + end) / 2);
for (var i = start; i < mid; i++) {
temp = arr[end - i - 1 + start];
arr[end - i - 1 + start] = arr[i];
arr[i] = temp;
}
};
function swap4(arr, x) {
reverse(arr, 0, x);
reverse(arr, x, arr.length);
reverse(arr, 0, arr.length);
return arr;
}
性能对比
jsper的测试结果:http://jsperf.com/reversea
从上面的数据看来单位时间内,swap4的性能最好了(果然机智),用js原生的方法则最差,比最快的慢了80%多。swap2在执行上也很快,但多用了一块空间来存放待偏移的temp字符,以空间换时间。swap3性能一般,比较依赖于x的位置,x的位置越靠后,需要花费的时间会越长。
还有一种巧妙的方法
巧妙的杂技表演
先将x[0]移到临时变量t中,再把x[i]移到x[0]腾出来的位置中,x[2i]移到x[i]中,以此类推(每一次移动时将x[]中的下标对其长度n取模),直到又回到从x[0]提取元素,此时应该把临时变量t放入到上一个位置中,并开始下一次迭代,即对x1进行类似的操作。找来书中直观的图如下:
代码如下:
function reverse(arr, m){
var k = 0;
for(var i = 0; i < m; i++){
k = 1; //每次迭代都从1倍位移开始
var temp = arr[i];
while(( k * m + i) % arr.length !== i){
arr[( k - 1 ) * m + i] = arr[k * m + i];
k++;
}
arr[(k - 1) * m + i] = temp;
}
}
但这种方法有限制性,如果数组的长度不能整除m,则无法正常的运行。
本文为原创文章,可能会经常更新知识点以及修正一些错误,因此转载请保留原出处,方便溯源,谢谢合作
本文地址:https://www.iamaddy.net/2017/08/string-reversal-algorithm/
个人知乎,欢迎关注:https://www.zhihu.com/people/iamaddy
欢迎关注公众号【入门游戏开发】
近期评论