27. 移除元素
题目描述
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
方法1
思路
记录一个删除元素后的数组长度len
如果相等将最后一个元素值赋值给当前元素,len-1
返回len即可
代码
package easy.移除元素27;
class Solution {
public int removeElement(int[] nums, int val) {
if (nums.length == 0) return 0;
//记录删除元素后的数组长度
int len = nums.length;
//循环查询
for (int i = 0; i < len; i++) {
if (nums[i] == val) {
//如果最后一个数等于val,len--,且最后一个元素不能是当前元素
while (i != len - 1 && nums[len - 1] == val) len--;
//如果值相等,将最后一个值赋值给当前
nums[i] = nums[len - 1];
//数组长度-1
len--;
}
}
return len;
}
}
方法2 双指针
思路
如果左指针 left 指向的元素等于 val,此时将右指针 right 指向的元素复制到左指针 left 的位置,然后右指针 right 左移一位。
如果赋值过来的元素恰好也等于 val,可以继续把右指针 right 指向的元素的值赋值过来
(左指针 left 指向的等于 val 的元素的位置继续被覆盖),直到左指针指向的元素的值不等于 val 为止。
代码
package easy.移除元素27;
class Solution2 {
/**
* 双指针方法
*
* @param nums
* @param val
* @return
*/
public int removeElement(int[] nums, int val) {
//记录删除元素后的数组长度
int left = 0;
int right = nums.length;
//循环
while (left < right) {
if (nums[left] == val) {
//如果值相等,将最右边的值赋值给当前元素,右区间-1
nums[left] = nums[right - 1];
right--;
} else {
//如果不相等,左区间+1
left++;
}
}
return left;
}
}