LeetCode 27. 移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 **原地 **修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1：

输入：nums = [3,2,2,3], val = 3

输出：2, nums = [2,2]

解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。

例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2

输出：5, nums = [0,1,4,0,3]

解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

解题思路

拿到这道题的第一直觉就是把重复元素删除，但是题目要求使用 O(1) 的空间，这就意味着我们一边遍历原数组，然后也不能用多余的空间来存元素，挨个比较元素，发现重复元素然后删除。

考虑到数组的内存是连续空间，既然不能开拓新的空间，那就能想到一定是覆盖。

一、暴力解法

用两个 for 循环：一遍循环遍历，一遍循环移动元素往前，也就是往前整体移动数组。这里用 C++ 实现：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();

        for (int i = 0; i < size; i++) {
            if (nums[i] == val) {
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 下标i以后的数值都往前移动了一位，所以i也减少，位置往前移动
                size--;
            }
        }
        return size;
    }
};

这种方法会的时间复杂度： $O(n^2)$，空间复杂度： $O(1)$

二、双指针

双指针法。此题用快慢指针法：通过一个快指针和慢指针再一个 for 循环完成两个循环的工作，

快指针遍历整个数组，遇到与给定元素不相同的元素就复制到慢指针指向的位置，然后让慢指针向前走一步。循环结束时慢指针指向的数组下标就是删除完成后的数组长度即可。

用 Go 语言实现方法如下：

func removeElement(nums []int, val int) int {
    slow := 0
    for _, v := range nums {
        if v != val {
            nums[slow] = v
            slow++
        }
    }
    return slow
}

一次循环，时间复杂度： $O(n)$，空间复杂度: $O(1)$

三、双指针优化

双指针还是很好理解的，等有空的时候画个图。但是针对某些情况还是有优化的空间。

举个例子：

输入参数：
nums:  []int{1,2,3,4,5}
val: 6

上述例子中，即使 nums 数组中没有等于 val 的元素，我们在遍历数组时仍然需要将数组中的每个元素都重新赋值。

换句话说即使上面我们的算法复杂度是O(n)，但是实际上还是有一些不必要的赋值操作，影响整体算法效率。

观察到题目中不要求输出元素的顺序，因此可以使用双指针数组元素的高效移动：初始化时左指针指向数组起始位置，右指针指向数组结束位置。 左指针遍历数组元素时，如果找到等于 val 的元素，则将左右指针指向的元素进行调换。当左右指针相遇时，遍历结束。

代码及注释如下:

func removeElement(nums []int, val int) int {
	l, r := 0, len(nums)-1 //左指针指向数组起始位置，右指针指向数组结束位置
	for l <= r {
		if nums[l] == val { //当左指针指向的元素等于val时
			nums[l] = nums[r] //交换左右指针的值
			r--
		} else { //这里要注意：如果左指针对应的元素被修改过的情况下，左指针不能右移，因为需要考察被换过来的元素
			l++
		}
	}
	return r+1
}

题目来源：力扣（LeetCode）
题目链接：https://leetcode-cn.com/problems/remove-element
优化思路来自作者：wei-ping-9
题解链接：https://leetcode-cn.com/problems/remove-element/solution/golangti-jie-by-wei-ping-9-qpqk/