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;
}