数组 - LeetCode 27. 移除元素
2023-10-25 本文已影响0人
我阿郑
给你一个数组 nums
和一个值 val
,你需要 原地
移除所有数值等于 val
的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,必须仅使用 O(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],也会被视作正确答案。
输入: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。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。
方法一:双指针
由于题目要求删除数组中等于 val
的元素,因此输出数组的长度一定小于等于输入数组的长度,我们可以把输出的数组直接写在输入数组上。
使用左右双指针:right
指针指向当前将要处理的元素,left
指针指向下一个将要赋值的位置。
- 如果
right
指针指向的元素不等于val
,它一定是输出数组的一个元素,将right
指针指向的元素复制到left
指针位置,然后将left,right
指针同时右移 - 如果
right
指针指向的元素等于val
,它不能在输出数组里,此时left
指针不动,right
指针右移一位
最坏情况:输入数组中没有元素等于val,左右指针各遍历了数组一次
IMG_1F8B9E92F4A2-1.jpeg区间 [0,left)
左闭右开 ,最后left的值就是输出数组的长度。
class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
int left = 0;
for (int right = 0; right < n; right++) {
if (nums[right] != val) {
nums[left] = nums[right];
left++;
}
}
return left;
}
}
- 时间复杂度:O(n),其中 n 为数组长度。
- 空间复杂度:O(1),我们只需要常数的空间保存若干变量。
方法二:双指针优化
如果要移除的元素恰好在数组的开头,例如数组 [1,2,3,4,5]
,当val为1时,我们需要把每一个元素都左移一位。
注意到题目中说:「元素的顺序可以改变」。实际上我们可以直接将最后一个元素5移动到数组开头,取代元素 1,得到序列[5,2,3,4]
同样满足题目要求。这个优化在数组中 val元素的数量较少时非常有效。
依然使用双指针实现:两个指针初始时分别位于数组的首、尾,向中间移动遍历该数组。
IMG_9F50C76D2332-1.jpegclass Solution {
public int removeElement(int[] nums, int val) {
if (nums.length == 0) {
return 0; // [] case , 不加这个容错nums[left]就会数组越界报错
}
int left = 0;
int right = nums.length - 1;
while(left < right) {
if(nums[left] == val) {
nums[left] = nums[right];
right--;
} else {
left++;
}
}
if(nums[left] == val) {
return left;
} else {
return left+1;
}
}
}
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0;
int right = nums.length;
// 左,右指针重合的时候,遍历完数组中所有的元素。
while (left < right) {
if (nums[left] == val) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
}
}
- 时间复杂度:O(n),其中 n 为数组长度。只需要遍历该数组至多一次。
- 空间复杂度:O(1),我们只需要常数的空间保存若干变量。