一、题目描述
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k,要通过此题,您需要执行以下操作:
- 更改 nums 数组,使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
- 返回 k。
二、测试用例
示例 1:
输入:nums = [3,2,2,3], val = 3
输出:2, nums = [2,2,_,_]
解释:你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要(因此它们并不计入评测)。
示例 2:
输入:nums = [0,1,2,2,3,0,4,2], val = 2
输出:5, nums = [0,1,4,0,3,_,_,_]
解释:你的函数应该返回 k = 5,并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要(因此它们并不计入评测)。
二、解题思路
- 基本思路:题目允许元素顺序发生改变,那么,可以使用不需要删除的元素来填充需要删除的元素,来避免移动大量元素。
- 具体思路:
- 双指针:维护两个指针 i 和 k ,初始化为 0 。指针 i 用于遍历数组,寻找不需要删除的元素,指针 k 用处存放不需要删除的元素,每次指针 i 找到不需要删除的元素,便赋值给指针 k ,直到遍历结束。【最坏情况,遍历两次序列,指针 i 一次,指针 k 一次】
- 快排思想:借助快排思想,将序列划分为左右两个部分,左边存放不需要删除的元素,右边存放需要的删除的元素。也是维护两个指针 i 和 k ,不过指针 i 初始化为 0 ,用于寻找需要删除的元素;指针 k 初始化为序列最后一个元素的位置,用于寻找不需要删除的元素;一旦两个指针都找到对应元素,便将指针 k 所指的元素赋值给指针 i ,然后继续寻找,直到两个指针相遇。【只遍历一遍序列】
三、参考代码
3.1 双指针
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
最好情况:遍历一遍序列,即删除全部元素,只有指针 i 移动。
最坏情况:遍历两遍序列,即不需要删除元素,指针 i 和 k 都需要移动
int removeElement(vector<int>& nums, int val) {
int n=nums.size();
int k=0;
for(int i=0;i<n;i++){
if(nums[i]!=val){
nums[k++]=nums[i];
}
}
return k;
}
3.2 快排思想
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
最坏和最好情况都是遍历一遍序列。
int removeElement(vector<int>& nums, int val) {
int k=nums.size()-1;
int i=0;
while(i<=k){
while(i<=k&&nums[i]!=val) i++;
while(i<=k&&nums[k]==val) k--;
if(i>k) break;
nums[i]=nums[k];
k--;
}
return k+1;
}