原地算法

原地算法

在计算机科学中，一个原地算法（in-place algorithm）是一种使用小的，固定数量的额外之空间来转换资料的算法。当算法执行时，输入的资料通常会被要输出的部份覆盖掉。不是原地算法有时候称为非原地（not-in-place）或不得其所（out-of-place）。

简单来说，就是在不新建大量额外空间（就是固定空间，无论数据多大，都不改变的那种）的基础上对原数据进行操作。

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：["h","e","l","l","o"]

输出：["o","l","l","e","h"]

示例 2：

输入：["H","a","n","n","a","h"]

输出：["h","a","n","n","a","H"]

public void reverseString(char[] s) {
    int len = s.length;
    for(int i =0;i<len/2;i++)
    {
        char temp = s[len-i-1];
        s[len-i-1] = s[i];
        s[i] = temp;
    }
    
}

补充

补充：原地算法（in-place algorithm）的关键判定标准是额外空间复杂度 O(1)（即与输入规模无关的固定少量变量），而不是"完全没有额外变量"。交换两个元素时用的 temp 变量不算违反原地。

经典原地算法举例：

• 数组反转、双指针交换（O(1) 额外）。
• 快速排序的 partition 过程（O(1) 额外，但递归栈 O(log n)）。
• 堆排序（O(1) 额外）。
• 翻转字符串 LeetCode 344：

function reverseString(s) {
  let l = 0, r = s.length - 1;
  while (l < r) {
    [s[l], s[r]] = [s[r], s[l]];
    l++; r--;
  }
}

非原地（out-of-place）例子：归并排序需要 O(n) 辅助数组；map / filter / slice 等返回新数组的方法。

来源整理自：我的有道云笔记