E
EdwardWong
V1
2022/09/15阅读:43主题:姹紫
LeetCode 27 移除元素
LeetCode 27 移除元素
题目示例:
给你一个数组nums
和一个值val
,你需要 原地 移除所有数值等于val
的元素,并返回移除后数组的新长度.
不要使用额外的数组空间,你必须仅使用 O(1)
额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例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,4,0,3]
解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素
解题思路
暴力算法
本题可以使用暴力算法,使用双层for
循环,时间复杂度是O(n^2)
,空间复杂度为O(1)
。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
//暴力算法
int size=nums.size();
for(int i=0;i<=size-1;i++){
if(nums[i]==val){
for(int j=i+1;j<=size-1;j++){
nums[j-1]=nums[j];
}
i--; //此时需要注意要将循环变量i的值减少1,因为整体向前移动了一位,后面在执行完if操作后会进行i++的操作
size--; //也要注意移除了一个元素后,这个size变量需要减少1,否则会出现数组越界的情况
}
}
return size;
}
};
Note: 注意移除元素之后,要对
size
和i
减一。
快慢指针
使用双指针从而可以写一层for
循环,其中快指针指向数组的元素值,慢指针记录更新数组的下标位置。
-
如果快指针指向的元素不等于
val
,它一定是输出数组的一个元素,我们就将快指针指向的元素复制到慢指针的位置,然后将快慢指针同时右移; -
如果快指针指向的元素等于
val
,需要移除此元素,并将慢指针的位置保持不动。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
//使用双指针解题可以只使用一层循环解决问题
int slow =0;
if(nums.size()==0) return 0;
for(int fast=0;fast<=nums.size()-1;fast++){ // i是快指针
if(nums[fast]!=val){ //如果快指针指向的数组元素等于要移除的目标值,那么快指针继续向后走,慢指针维持不动,如果指向的数组元素不等于要移除的目标值,那么快慢指针都向前移动
nums[slow]=nums[fast];
slow++;
}
}
return slow;
}
};
优化双指针
对于第二种方法,快慢指针都要循环遍历数组一次,为了减少循环遍历的次数,可以将左指针指向数组的左边,右指针指向数组的右边。
-
如果左指针指向的元素等于 val
,那么将右指针指向的数组元素赋值给左指针指向的数组元素,然后向左移右指针。 需要注意的是,此时左指针刚刚被赋予的新元素仍然可能为val,还要进行判断, 直至当左指针的元素值不等于val
,左指针向右移。
C++ 版本
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
//使用双指针的优化,慢指针指向数组前半段,快指针指向数组后半段
int left=0;
int right=nums.size();
while(left<right){ //用for循环不好确定终止循环条件,此时使用while循环非常方便,当慢指针向右走,快指针向左走,两个指针相等的时候,就终止循环
if(nums[left]==val){
nums[left]=nums[right-1];
right--;
}else{
left++;
}
}
return left;
}
};
Python版本
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
left=0
right=len(nums)-1
## 需要判断nums数组是否为空,如果为空的话直接返回0
if (right==-1):
return 0
while(left<=right):
if(nums[left]==val): ## 如果左指针指向的元素等于val,那么把右指针指向的元素复制到左指针的位置
nums[left]=nums[right]
right-=1
left-=1
left+=1
return left
作者介绍
E
EdwardWong
V1