seo搜索引擎优化培训班_企业网站建设合同电子版_如何制作自己的链接_网络公司排行榜

题目描述

给你一个数组 nums 和一个目标值 val，你需要原地移除数组中所有等于 val
的元素，返回移除后数组的新长度，且元素的相对顺序应该与原数组一致。

示例

示例 1

输入: nums = [3,2,2,3], val = 3
输出: 2, nums = [2,2]
解释: 我们从数组中移除了两个 3，新的长度应该是 2，并且数组中剩下的元素应该是 [2,2]。

示例 2

输入: nums = [0,1,2,2,3,0,4,2], val = 2
输出: 5, nums = [0,1,4,0,3]
解释: 我们从数组中移除了三个 2，新的长度应该是 5，并且数组中剩下的元素应该是 [0,1,4,0,3]。

题解

这个问题可以通过双指针法来解决。我们使用一个指针 i 来遍历数组，另一个指针 k 来记录不等于 val 的元素应该插入的位置。

1. 初始化：设置 k 为 0。
2. 遍历数组：从数组的第一个元素开始遍历（索引为 0）。
3. 更新元素：对于每个元素，如果它不等于 val，则将其复制到 k 索引处，并将 k 加 1。
4. 返回结果：遍历结束后，k 就是不等于 val 的元素的个数。

代码实现

int removeElement(vector<int>& nums, int val) {int k = 0;for (int i = 0; i < nums.size(); i++) {if (nums[i] != val) {nums[k++] = nums[i];}}return k; // 返回不等于 val 的元素的个数
}

复杂度分析

● 时间复杂度：O(n)，其中 n 是数组 nums 的长度。我们需要遍历一次数组，并且对于每个元素，我们进行常数时间的操作。
● 空间复杂度：O(1)，因为我们是在原地修改数组，没有使用额外的空间。
这个算法的优势在于它不需要额外的数组空间，并且时间效率较高。通过使用双指针法，我们可以在一次遍历中完成删除特定值元素的操作，同时保持元素的相对顺序。