算法描述
首先是摘自维基百科的描述：
原地算法是基本上不需要借助额外的数据结构就能对输入的数据进行变换的算法。不过，分配少量空间给部分辅助变量是被允许的。算法执行过程中，输入的数据往往会被输出结果覆盖。原地算法只能通过替换或交换元素的方式来修改原始的输入。
可以说，原地算法是空间复杂度上非常理想的一类算法，而且由于内存的分配与释放也是非常耗时的环节，原地算法甚至有可能还会有时间上的优势。不过一般来说，想要满足O(1)的空间复杂度非常困难，所以，一般认为满足O(logn)的就可以称之为原地算法。同时，这不是某个具体的算法，而是一类算法的统称。
部分场景
这些是目前记录下来可以用原地算法的场景，如果有需要内存限制比较严格的条件下实现相似功能，可以就这么用。
1.数组翻转
要求：
给定一个n元素的数组A，将数组的所有元素逆序排列。
简单实现：
创建一个大小相同的数组，然后将输入 a 中的元素按照恰当的顺序复制到新数组中，最后删除 a。(C++版本)
template<typename T>
function reverse-in-place(a[0..n])
for i from 0 to floor(n/2)
tmp := a[n-i]
a[i] := a[n-i]
a[n-i] := tmp
原地算法实现：
2.矩阵旋转
给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。不占用额外内存空间能否做到？
旋转后，对于矩阵中第 i 行的第 j个元素，在旋转后，它出现在倒数第 i 列的第 j个位置。
即matrix[col][n−row−1]=matrix[row][col]。
如果是原地旋转，一次需要转四个角。也就是说，遍历时需要遍历四分之一的坐标，这些坐标在旋转过程中没有重合且旋转四次会覆盖整个矩阵。
下列代码采用的是第一种。
void rotate(vector<vector<int>>& matrix) {
int N=matrix.size(),temp;
for(int row=0;row<N/2;row++){
for(int col=row;col<=N-row-2;col++){
temp=matrix[row][col];
matrix[row][col]=matrix[N-col-1][row];
matrix[N-col-1][row]=matrix[N-row-1][N-col-1];
matrix[N-row-1][N-col-1]=matrix[col][N-row-1];
matrix[col][N-row-1]=temp;
}
}
}
此外，水平轴翻转后再主对角线翻转，也可以得到要求的结果。
3.二叉树转链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
展开后的单链表应该同样使用TreeNode其中right子指针指向链表中下一个结点，而左子指针始终为null。
展开后的单链表应该与二叉树先序遍历顺序相同。
https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
原理：由于前序遍历访问各结点的顺序是根节点、左子树、右子树。因此右子树访问前的前驱结点是左子树最右的结点。
因此设置三个指针cur、next、pre。处理cur的左子树，next指向cur的左节点。如果next不存在，那么没有左子树也就前驱结点，不需要处理。pre指向cur的左子树的最右结点，将pre指向cur的右子树。最后，再将cur的左子树移到右子树，cur向其右孩子移动一步。
原地算法实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
void flatten(TreeNode* root) {
TreeNode *cur = root;
while (cur != nullptr) {
if (cur->left != nullptr) {
TreeNode* next = cur->left;
TreeNode* predecessor = next;
while (predecessor->right != nullptr) {
predecessor = predecessor->right;
}
predecessor->right = cur->right;
cur->left = nullptr;
cur->right = next;
}
cur = cur->right;
}
}
有的原地算法实现虽然不声明新的数据，但是由于过程涉及递归，程序还需要开辟栈空间，因此还是O(n)的空间复杂度，这种情况可以将递归分解。
最大子数组和
给你一个整数数组 nums,请你找出一个具有最大和的连续子数组（子数组最少包含一个元素）,返回其最大和。子数组是数组中的一个连续部分。
运用简单动态规划的方式，设数组为nums，可以设置f(i)为“第i个数为结尾的子数组的最大和”，那么最大子数组和即为max(f(i))(1<=i<=nums.size())。
状态转移方程：f(i)=max{f(i−1)+nums[i],nums[i]}。即最大值要么是以i-1结尾子数组加上nums[i],要么是nums[i]。对于这类简单动态规划，可以用O(1)的空间来维护之前的值。
原地算法实现：
int maxSubArray(vector<int>& nums) {
int pre = 0, maxAns = nums[0];
for (const auto &x: nums) {
pre = max(pre + x, x);
maxAns = max(maxAns, pre);
}
return maxAns;
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
如果有任何有错误或不够清晰的表达，欢迎邮件至 passacaglia@88.com，谢谢！