Python中数组原地移除指定元素的时间与空间复杂度确认

你的复杂度分析完全正确，具体拆解如下：

• 空间复杂度O(n)：nums[:]会创建原数组的完整副本，需要占用与原数组相同的内存空间，因此空间复杂度为O(n)。
• 时间复杂度O(n²)：遍历副本的操作是O(n)，但每次调用nums.remove(value)时，列表需要先找到目标元素（最坏O(n)），然后将该元素之后的所有元素向前移动一位（也是O(n)）。如果数组中有k个等于val的元素，总时间开销就是O(n + k*n)，最坏情况下k=n，总时间复杂度退化为O(n²)。

优化解法（O(n)时间 + O(1)空间） #

可以用双指针法实现原地修改，完全符合题目要求的“原地操作”且效率更高：

def removeElement(nums, val):
    k = 0
    for i in range(len(nums)):
        if nums[i] != val:
            nums[k] = nums[i]
            k += 1
    return k

这个思路是用慢指针k记录有效元素的位置，快指针i遍历整个数组，遇到不等于val的元素就把它放到慢指针的位置，最后k就是有效元素的个数，全程不需要额外创建数组副本，也没有高开销的remove操作。

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