LeetCode - 移除元素

一. 题目描述

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

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

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

示例 1:

给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

二. 我的解法

2.1 代码

  今天这个题目我也看了不少其他人的代码，出于对性能和可读性上来考虑的话，还是我的代码要更好一些，不过也是因为在LeetCode也只能看到部分代码的关系，并不能看到更多的其他的人的代码了，所以我厚颜无耻且自信地认为这是我目前看到的最好的解决方案。

class Solution {
public int removeElement(int[] nums, int val) {
int pre = 0;
for( int i = 0; i < nums.length; i++ )
{
if( nums[i] != val )
{
nums[pre] = nums[i];
pre += 1;
}
}
return pre;
}
}

2.2 分析

1.在讲这个代码之前， 我觉得有必要先看另外一道题的解法，看不懂以上代码的同学可以先看第三节中介绍的另一个题目。

2.看了第三节的同学再来看这段代码，应该就会觉得很好理解了，没错，都是一样的套路，就是不仅将原数组的数组都拿出来用，同时也认为原数组中每个位置都是空的。

3. 为什么可以这么认为呢？首先，从预期的结果，也就是我们整个程序执行完成之后nums的结果，如题目描述中示例1中，运行后，nums=[2, 2, 2, 3]，有些同学可能会问，结果中还是存在3，这里，我需要说：请注意审题！！“你不需要考虑数组中超出新长度后面的元素。”也就是说， 外部的程序会自动按照他预期的结果长度来截取你返回的数组，所以，只要把需要的提前或者是不要的后置就可以了，我们采用的就是需要的提前的法子。

4. 既然已经知道了运行结果了， 那么再来讲解一下， 博主是怎么想到用这个方法的，很显然， 我是做了下面第三节描述的那道题之后才做的这道题，所以， 很容易就想到了这个方法，哈哈哈。

5. 不皮了，讲一下这么遍历操作的合理性，很显然，前面我们已经说过了，我们是采用将需要的数据提前的方法，那么正常的思路当然是，正向去遍历，然后找到一个需要的就往前面放，并放在上一个放置好的元素后一位，那么这么去操作的话，结果数组中的所有元素的原位置肯定不会比当前位置要大，也就是说， 在原数组中的元素要么已经在它未来的位置，要么就是在未来位置的后面，已经在未来位置上了的，表明在遍历过程中不会被移动，而不在位置上的将会被提前，而提前的元素并不会影响后面需要的元素，由于是正向遍历，也表明当前元素之前的元素已经提前完毕，所以，博主判断第三节的方法用在这道题是可行的，然后一试，果然通过了。

三. 删除排序数组中的重复项

3.1 问题描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

3.2 代码

class Solution {
public int removeDuplicates(int[] nums) {
int pre = 0;
for(int i = 1; i < nums.length; i++)
{
if( nums[i] != nums[pre] )
{
pre += 1;
nums[pre] = nums[i];
}
}
return pre + 1;
}
}

3.3 分析

1.  是不是觉得这个代码跟上一题的代码非常像，不过这道题想到这么写就要简单得多了。

2. 思路很简单，既然数组已经是排序好了的，那么我只需要记住第一次出现这个数字的位置，如果这个数字继续出现，就继续遍历，如果出现新的数字，就让当前索引位置加 1 ， 并将这个新出现的数字放置在当前位置上；接着重复以上的操作即可。

3.  跳过来看的同学可以跳回第二节了。

四. 参考

https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/description/

https://leetcode-cn.com/problems/remove-element/description/

最后

以上就是迷你保温杯为你收集整理的LeetCode - 移除元素的全部内容，希望文章能够帮你解决LeetCode - 移除元素所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。