修改给定输入数组解题时，空间复杂度是O(n)还是常数级？

首先给出明确结论：这种情况下空间复杂度仍然属于常数级（O(1)），不会因为修改输入数组被判定为O(n)。

相关判定规则说明：

• 算法复杂度分析体系里的空间复杂度，统计的是除题目给定的输入数据本身占用空间之外，你实现算法时额外申请的临时存储空间大小，输入数据的空间成本不算在算法的空间开销内。
• 你提到的仅修改原输入数组、没有额外申请其他空间的实现，属于标准的原地（in-place）算法，这类算法的空间复杂度默认按O(1)判定，是行业通用的统计规则。
• 只有当你额外申请了和输入规模n成正比的存储空间（比如额外新建了一个长度为n的数组存中间结果），才会被判定为空间复杂度O(n)。

举个常见的参考案例：各算法刷题平台上的「移除元素」「颜色分类」等允许修改输入数组的题目，所有原地修改的题解都会被判定为O(1)空间复杂度。

内容的提问来源于stack exchange，提问作者Lame Things