如何优化removeElement函数代码以降低时间复杂度？

你的当前代码时间复杂度是O(n log n)，瓶颈在于最后的排序步骤。我们可以用双指针法把时间复杂度降到O(n)，同时满足原地修改数组、返回非val元素个数的要求。

核心思路：快慢双指针 #

用一个慢指针记录非val元素的存放位置，快指针遍历整个数组：

• 快指针遇到不等于val的元素时，将其赋值给慢指针的位置，慢指针右移；
• 快指针遇到val时直接跳过，继续遍历。
  遍历结束后，慢指针的位置就是非val元素的个数k，且nums的前k个元素已经是处理好的非val元素。

优化后的代码 #

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = 0
        for fast in range(len(nums)):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
        return slow

进阶优化：左右双指针（适用于val元素较少的场景） #

如果数组中val元素占比很低，可以用左右指针交换的方式减少赋值操作：

• 左指针从左往右找第一个等于val的元素；
• 右指针从右往左找第一个不等于val的元素；
• 交换两者位置，直到左右指针相遇。
  最终左指针的位置就是非val元素的个数。

代码示例：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            if nums[left] == val:
                nums[left] = nums[right]
                right -= 1
            else:
                left += 1
        return left

复杂度对比 #

• 原代码：遍历O(n) + 排序O(n log n)，整体O(n log n)；
• 双指针法：仅一次遍历，整体O(n)，空间复杂度都是O(1)，完全符合题目约束，效率更优。

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