移除数组元素

问题

https://leetcode-cn.com/problems/remove-element

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例1：

给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:

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

解法

元素替换

1. 使用一个指针指向 nums 首位
2. 遍历 nums，元素不等于 val 时，将指针位置的值替换为该元素，指针往后移动。
3. 重复步骤2
4. 最后指针指向的位置的前面就都为移除 val 后的元素。指针指向的下标值即为所求长度

func removeElement(nums []int, val int) int {
	if nums == nil || len(nums) == 0 {
		return 0
	}

	result := 0
	for _, item := range nums {
		if item != val {
			// 找到一个不为指定值的元素，写到数组前面
			nums[result] = item
			// 指针往后走
			result++
		}
	}
	// [0 1 3 0 4 0 4 2]
	fmt.Printf("%v", nums)
    // 最后，result指向的位置的前面均为去除 val 的元素，result的值也即所需的长度
    // 5
	return result
}

这个方法其实与 有序数组去重 中的快慢指针方法本质相同。

时间复杂度 \(O(n)\)，空间复杂度 \(O(1)\)。

交换移除

这种方式本质也是循环数组，当遇到值为 val，把 nums 末尾的元素交换到遍历的位置。

func removeElement2(nums []int, val int) int {
	if nums == nil || len(nums) == 0 {
		return 0
	}

	left, right := 0, len(nums)

	for left < right {
		if nums[left] != val {
			// 不相等，左指针往后走
			left++
		} else {
			// 相等，左指针向前走
			right--
			nums[left] = nums[right]
		}
	}

	fmt.Printf("%v", nums)
	return right
}

时间复杂度 \(O(n)\)，空间复杂度\(O(1)\)，遍历的次数要比上面的方法要少。