27 移除元素
本题重点:数组删除第i个元素的方法:将i之后的元素依次左移1位
暴力做法
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int size = nums.size();
for(int i = 0; i < size; i++){
// 找到数值等于val的元素
if(val == nums[i]){
// 数组删除第i个元素的方法:将i之后的元素依次左移1位
for(int j = i + 1; j < size; j++){
nums[j - 1] = nums[j];
}
// 删除第i个元素,第i个元素变成新元素,下一次依然从i开始遍历
i--;
// 删除元素后,数组大小减1
size--;
}
}
// 数组剩余的都是不等于val的元素
// 因此返回数组大小即可
return size;
}
};
时间复杂度:\(O(n^2)\)
空间复杂度:\(O(1)\)
双指针法
和数组去重思路几乎一样
注意分辨题意和slowIndex初始化的含义,这决定了slowIndex++放在nums[slowIndex] = nums[fastIndex]之前还是之后
在本题中,需要删除等于val的元素, 如果slowIndex = 0,说明我们默认第一个元素不等于val,这就需要
如果slowIndex = -1,说明我们默认第一个元素不确定是否等于val,接下来我们需要维护第一个元素使其不等于val,那么需要
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
// 慢指针指向新数组末尾元素的下一个位置(插入的位置)
// 新数组元素:数值不等于val的元素
int slowIndex = 0;
// 快指针指向从左到右数值不等于val的第一个元素
for(int fastIndex = 0; fastIndex < nums.size(); fastIndex++){
if(val != nums[fastIndex]){
// 如果fastIndex指向的元素不等于val,需要将其加入到新数组中
nums[slowIndex] = nums[fastIndex];
slowIndex++;
}
}
// 慢指针指向新数组末尾元素的下一个位置
// 因为元素索引从0开始,所以slowIndex就是元素个数
return slowIndex;
}
};
时间复杂度:\(O(n)\)
- 只遍历了一次数组
空间复杂度:\(O(1)\)