JS 的原地(in-place)算法实践

by Jack Pu

In computer science, an in-place algorithm is an algorithm which transforms input using no auxiliary data structure. However a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. In-place algorithm updates input sequence only through replacement or swapping of elements. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.

像 wiki 里面说的，原地算法是基本上不需要额外辅助的数据结构,然而,允许少量额外的辅助变量来转换数据的算法。在计算复杂性理论中，原地算法包含使用O(1)空间复杂度的所有算法，DSPACE(1)类型。

 function reverse-in-place(a[0..n])
     for i from 0 to floor(n/2)
         swap(a[i], a[n-i])

数组翻转

比如我们在 JS 中，实现翻转数组，（array.prototype.reverse） 除外。

[1,2,3] => [3,2,1]


function reverseArray(arr) {
  var len = array.length;
  var middle = Math.floor(len / 2);
  for (var i = 0; i < middle; i += 1) {
     var temp = array[i];
     array[i] = array[n - 1 - i];
     array[n - 1 - i] = temp;
  }
}

这样我们就不用借助另外一个一个数组倒序循环了。

删除排序后数组的重复元素

比如我们给出一组排好后的数组，然后删除掉其中重复的元素

[1,2,3,3,3,4,5,5,5,6,7]
=>
[1,2,3,4,5,6,7]

var removeDuplicates = function(nums) {
	var i = 0;
    for (n of nums) {
      if (i==0 || n > nums[i - 1]) {
	    nums[i++] = n;
	  }
    }
    return i;
};

判断回文

最近 20200202 比较火，这是比较常见的回文数字。类似单词比如 bob 或者句子 Was it a car or a cat I saw?。

'aba' => true
'accad' => false
'20200202' => true

我们如何判断一个字符串是回文的时候可以用到。

function isPalindromeStr(str) {
  var middle= Math.floor(str.length / 2);
  for (var i = 0; i < middle; i++)
    if (str[i] !== str[str.length - i - 1]) {
		return false;
	}
     
  return true;
}