原地删除

01、题目分析

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

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

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

示例 1:

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

这道题比较简单哦,只要把握好“原地删除”这个关键字,就可以顺利求解啦!

具体过程如下图所示:

PNG

根据分析,我们可以得到下面的题解:

  1. //GO
  2. func removeElement(nums []int, val int) int {
  3. for i := 0; i < len(nums);{
  4. if nums[i] == val {
  5. nums = append(nums[:i],nums[i+1:]...)
  6. }else{
  7. i++
  8. }
  9. }
  10. retunums)
  11. }


和这道题类似的还有LeetCode 26题,大家可以尝试自己先做一做,然后再看答案哦。

02、类似题目分析

题目26:删除排序数组中的重复项
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次。

返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

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

示例 2:

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


这道题的重点是原地两个字,也就是要求必须在O(1)的空间下完成。并且题中已经告知了数组为有序数组,这样重复的元素一定是连在一起的,我们只需要一个一个移除重复的元素即可,具体方案方案怎么做,我们看看下面就会明白了。

移除的具体过程:

PNG

根据分析,我们可以得到下面的题解:

  1. //GO
  2. func removeDuplicates(nums []int) int {
  3. for i := 0; i+1 < len(nums);{
  4. if nums[i] == nums[i+1]{
  5. nums = append(nums[:i],nums[i+1:]...)
  6. }else{
  7. i++
  8. }
  9. }
  10. return len(nums)
  11. }


好啦,关于数组原地操作的两道题就讲到这里啦,如果大家有兴趣的话,可以参考做一下LeetCode 283题(移动O),也是一样的做法哦!