力扣26 - 删除有序数组中的重复项【快慢指针】

一、题目描述

原题传送门

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

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

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

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

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按 升序 排列

二、思路分析

好，看完题目的描述，我们来分析一下去求解这道题目

• 首先题目的意思是给你一个数组，这数组中可能有多个相邻重复元素，例如示例2中的【0 0 1 1 1 2 2 3 3 4】，这里的00,111,22,33，就是值得重复元素，我们要做的就是将多余的重复元素删去，最后剩余的结果就是对于这个数字，后面不可以出现与其相同的数，当然有其他数间隔不算
• 首先我想到的一个思路就是快慢指针，这个思路对于力扣27.移除元素同样适用，就是刚开始需要一个快指针，去遍历这个数组的所有元素，因为它越往后始终比慢指针快，所以叫它快指针；然后对于慢指针，就是用来更新新数组所需要使用的指针
• 具体的替换方式是当这个快指针和慢指针相同的时候，快指针++，将慢指针之后的元素过滤掉，然直至快指针的值和慢指针不相等后，首先让和这个慢指针++，然后将慢指针所在位置的值更新为快指针所在位置的值，然后快指针再++

三、步步算法图解展示

有了思路之后来分析一下

• 首先的话两个指针都是从0开始，这毋庸置疑，只有前后指针才是天各一方
• 然后的话就是循环内部的逻辑，刚才在描述思路的时候有说到过，就是通过一个判断，若是快指针所指元素的值与慢指针不一样时，则进行一个元素的过滤，我们主要通过算法图解来演示一下

---

• 首先就是初始化的更新操作，我们以示例2作讲解

• 首先两个元素一致，src++

• 又一致，继续++，然后发现1 不等于 0

• 这里很重要的一点来了，对应下面这句代码，首先让dst++，然后将src所在位置的值赋值给到dst所在位置的值，接着src再++

nums[++dst] = nums[src++];
1

• 此处若是你要简写成我这样，就要将这个++写在dst之前，访问的才是++之后的值，若是将++放在后面，访问的就是++之前的位置了

• 然后发展一直相同，便继续遍历，知道遍历到2为止

• 然后就将dst++，一样进行一个赋值操作，src再++

• 发现一样继续++，知道==直到3 不等于 2

• 一样进行一个赋值操作，然后src继续向后遍历

• 有发现不一样就停下来赋值

• 然后直到这个src超过数组边界的时候，循环便结束，此时可以看到，前面的值进行了一个变化，为【0 1 2 3 4】，就是取出相邻重复元素之后的新数组

• 此时我们就需要返回这个数组的大小，那是返回dst吗，不，需要返回的是【dst + 1】的位置，因为数组下标是从0开始的，而此时dst所指的下标很明确，从数字就能看出来为4，但是数字个数为5，所以要返回【dst + 1】

简单地通过算法图解描述了一下，不知道你听懂没，如果没有再仔细读一下代码，然后自己动手画画图吧，说不定就能有思路了

四、整体代码展示

有了步步算法图解的分析，相信已经迫不及待想要写代码了，可以先去写写看再来看。我这里会给出很多版本

1、双指针【原始版】

• 首先就是最简单的版本，代码的可读性非常高，一目了然
• 主要就是nums[src] != nums[dst]这块，首先让dst++，然后做覆盖操作，接着再让src++

int removeDuplicates(int* nums, int numsSize){
    int src = 0, dst = 0;
    while(src < numsSize)
    {
        if(nums[src] == nums[dst])
            src++;
        else
        {
            dst++;
            nums[dst] = nums[src];
            src++;
        }
    }
    return dst + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2、双指针【简练版】

• 简练版的话就是将原始版的逻辑进行了一个拼接，因为dst++是在前头的，所以我们完全可以使用一个前置++来完成，src++是在后头的，所以可以使用后置++来完成

int removeDuplicates(int* nums, int numsSize){
    int src = 0, dst = 0;
    while(src < numsSize)
    {
        if(nums[src] == nums[dst])
            src++;
        else
            nums[++dst] = nums[src++];
    }
    return dst + 1;
}
1
2
3
4
5
6
7
8
9
10
11

3、双指针【精华版】

• 对于精华版的话就是对上面这个逻辑做一个整合，可以看到无论是对于相等还是不相等的情况，src++是一定会执行的，所以我们可以将其单独抽离出来，只需要去判断两者不相等的情况即可

int removeDuplicates(int* nums, int numsSize){
    int src = 0, dst = 0;
    while(src < numsSize)
    {
        if(nums[dst] != nums[src])
        {
            //若是发现不相等，则dst++然后覆盖为src位置上的值
            nums[++dst] = nums[src];
        }
        src++;      //src无论如何都要++
    }
    return dst + 1;     //最后返回的是去重后数组的个数，因此要 + 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4、双指针【src从1开始】✔

• 有同学说两个指针在一开始的时候多进行了一次判断，那可不可以让他们从直接从下标为1开始呢？我们来试试

int removeDuplicates(int* nums, int numsSize){
    int src = 1, dst = 0;
    while(src < numsSize)
    {
        if(nums[dst] != nums[src])
        {
            //若是发现不相等，则dst++然后覆盖为src位置上的值
            nums[++dst] = nums[src];
        }
        src++;      //src无论如何都要++
    }
    return dst + 1;     //最后返回的是去重后数组的个数，因此要 + 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5、双指针【dst从1开始】❌

int removeDuplicates(int* nums, int numsSize){
    int src = 1, dst = 1;
    while(src < numsSize)
    {
        if(nums[dst] != nums[src])
        {
            //若是发现不相等，则dst++然后覆盖为src位置上的值
            nums[++dst] = nums[src];
        }
        src++;      //src无论如何都要++
    }
    return dst + 1;     //最后返回的是去重后数组的个数，因此要 + 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 可以看到，当我零dst = 1时即让dst从1开始遍历时，在去重的过程中就无法实现我们想要的结果，第一个有重复的元素会被遗漏，所以对于dst不可以从1开始，只可以从0开始
  

五、总结与提炼

• 最后我们来总结一下本文所介绍的内容，本文讲解来一道力扣中有关数组元素删除的题目，删除的是相邻元素的值，我们使用到的是双指针，通过两个指针的不断交替变换，将快指针所指的位置赋给慢指针所在位置，就完成了相邻元素的删除【给出了不同的优化版本，任君挑选】

以上就是本文所要描述的所有内容，感谢您对本文的观看，如有疑问请于评论区留言或者私信我都可以🍀