平顶山有做网站的公司,东莞免费建站公司,设计自学网,广告设计图片创意代码随想录二刷 #xff5c; 数组 #xff5c; 移除元素 题目描述解题思路 代码实现暴力解法双指针法 题目描述
27. 移除元素
给你一个数组 nums 和一个值 val#xff0c;你需要 原地 移除所有数值等于 val 的元素#xff0c;并返回移除后数组的新长度。
不要使用… 代码随想录二刷 数组 移除元素 题目描述解题思路 代码实现暴力解法双指针法 题目描述
27. 移除元素
给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数但输出的答案是数组呢?
请注意输入数组是以「引用」方式传递的这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说不对实参作任何拷贝 int len removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i 0; i len; i) { print(nums[i]); }
示例 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,3,0,4] 解释函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
提示
0 nums.length 1000 nums[i] 500 val 100
解题思路 代码实现
暴力解法
使用两层for循环第一层遍历数组元素第二层更新数组
class Solution {
public:int removeElement(vectorint 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--; // 数组大小也需要-1}}return size;}
};时间复杂度O(n^2) 空间复杂度O(1) 双指针法
通过一个快指针和一个慢指针在一个for循环下完成两个for循环的工作。
快指针寻找新数组即不含目标元素的数组的元素慢指针指向更新新数组下标的位置
class Solution {
public:int removeElement(vectorint nums, int val) {int slowIndex 0;int size nums.size();for (int fastIndex 0; fastIndex size; fastIndex) {if (val ! nums[fastIndex]) {nums[slowIndex] nums[fastIndex];}}return slowIndex;}
};相对难理解的是这一句 nums[slowIndex] nums[fastIndex]; 它的意思是当没有找到值为val的元素时if语句的条件将fastIndex指向的元素赋给slowIndex指向的元素随后slowIndex向右移动一位。
它也等同于
nums[slowIndex] nums[fastIndex];
slowIndex;本题中双指针的目的是在原有数组的基础上重新构建一个不含目标值的新数组删除操作被巧妙的隐藏在了构建新数组中。
如果一直没遇到目标值每一次循环过后两个指针是始终指向同一个元素的如果遇到了目标值slow指向的元素依然是非目标值元素而fast指针会继续向前在下一次飞目标值的循环时slow指向的元素会重新获得fast指向的元素也就是说目标值没有被slow指向过他不在新构建的数组中。
举一个例子来帮助理解
一个数组如下需要移除的元素是值等于val也就是等于2的元素初始状态下fastIndex和slowIndex位置如下 在if (val ! nums[fastIndex)的条件下也就是下标0、1、2这三个位置
fastIndex 0nums[fastIndex] 1nums[slowIndex] nums[fastIndex]因此nums[slowIndex] 1slowIndex此时slowIndex 1循环体内结束最后fastIndexfastIndex 1.fastIndex 1nums[fastIndex] 3nums[slowIndex] nums[fastIndex]因此nums[slowIndex] 3slowIndex此时slowIndex 2循环体内结束最后fastIndexfastIndex 2.fastIndex 2nums[fastIndex] 3nums[slowIndex] nums[fastIndex]因此nums[slowIndex] 3slowIndex此时slowIndex 3循环体内结束最后fastIndexfastIndex 3.
此时的状态如下图 此时遇到了目标值不符合if的条件了因此fastIndex会直接1fastIndex 4而slowIndex依然为2: 接下来的循环中if条件又满足了所以 fastIndex4nums[fastIndex] 1nums[slowIndex] nums[fastIndex]所以nums[slowIndex] 1slowIndex 1 3。注意此时slowIndex指向了3而nums[slowIndex] 4也就是说原本的nums[3] 2变为了nums[slowIndex] 1就相当于删除了原本的nums[3] 2。此时的数组如下图可以看到nums[3] 2 已经被替代了 最后fastIndex1 5slowIndex 3。接下来全部都符合if的条件最后fastIndex来到末尾整个程序结束。
