淄博网站排名外包百度云盘资源共享链接群组链接

一、需求

• 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

• 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

• 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

二、双指针法

2.1  思路分析 

• 这个地方想复杂了，就当练习了； 

2.2  代码实现

class Solution {public int removeElement(int[] nums, int val) {int len = nums.length;int i = 0;while(i < len) {int j = i;if(nums[i] == val) {len--;while(j < len) {nums[j] = nums[j + 1];j++;}} else {i++;}}return len;}
}

2.3  复杂度分析

• 时间复杂度为，最坏情况下，数组中的元素全都与val相同；
• 空间复杂度为；

三、双指针法2

3.1  思路分析

1. 这个思路很简单，就是从头到尾遍历原数组，如果遇到与val不相等的元素，从原数组的索引0开始，依次把满足该条件的元素存储进去；
2. 每存进一个值，就累加一次当前新数组的长度；

3.2  代码实现

class Solution {public int removeElement(int[] nums, int val) {int len = 0;int k = 0;for(int num : nums) {if(num != val) {nums[k++] = num;len++;}}return len;}
}

3.3  复杂度分析

• 时间复杂度为O(N)，N为数组中元素的个数；
• 空间复杂度为O(1)；

四、双指针法3

4.1  思路分析

1. 当我们要删除的元素在数组中很少时，比如[1,2,3,4,5]，我们要删除1，那么那么方法3会对后4个元素执行移位赋值操作，我们要想办法来优化它；
2. 我们可以这样处理，在遍历数组过程中，如果遇到了待删除的元素，我们直接把它赋值为数组最后一个元素值，然后数组长度-1，那不就相当于删除它了吗？
3. 注意遍历过程中，数组的长度是随着步骤2动态变化的，因此当数组遍历结束后，我们返回数组的长度即可； 

4.2  代码实现

class Solution {public int removeElement(int[] nums, int val) {int i = 0;int n = nums.length;while(i < n) {if(nums[i] == val) {nums[i] = nums[n - 1];n--;} else {i++;}}return n;}
}

4.3  复杂度分析

• 时间复杂度为O(N)；
• 空间复杂度为O(1)；

五、学习地址

作者：LeetCode

链接：https://leetcode-cn.com/problems/remove-element/solution/yi-chu-yuan-su-by-leetcode/