概要
这是一个相当简单的问题,但人们可能会对“就地”一词感到困惑,并认为在不复制数组的情况下从数组中删除元素是不可能的。
提示
- 尝试双指针法。
- 你是否使用“元素顺序可以更改”这一属性?
- 当要删除的元素很少时会发生什么?
解决方案
方法一:双指针
思路
既然问题要求我们就地删除给定值的所有元素,我们就必须用 的额外空间来处理它。如何解决?我们可以保留两个指针 和 ,其中 是慢指针, 是快指针。
算法
当 与给定的值相等时,递增 以跳过该元素。只要 ,我们就复制 到 并同时递增两个索引。重复这一过程,直到 到达数组的末尾,该数组的新长度为 。
该解法与 删除排序数组中的重复项 的解法十分相似。
复杂度分析
-
时间复杂度:, 假设数组总共有 个元素, 和 至少遍历 步。
-
空间复杂度:。
方法二:双指针 —— 当要删除的元素很少时
思路
现在考虑数组包含很少的要删除的元素的情况。例如,。之前的算法会对前四个元素做不必要的复制操作。另一个例子是 。似乎没有必要将 这几个元素左移一步,因为问题描述中提到元素的顺序可以更改。
算法
当我们遇到 时,我们可以将当前元素与最后一个元素进行交换,并释放最后一个元素。这实际上使数组的大小减少了 1。
请注意,被交换的最后一个元素可能是您想要移除的值。但是不要担心,在下一次迭代中,我们仍然会检查这个元素。
复杂度分析
-
时间复杂度:, 和 最多遍历 步。在这个方法中,赋值操作的次数等于要删除的元素的数量。因此,如果要移除的元素很少,效率会更高。
-
空间复杂度:。