双指针解决去重问题

发布: 分类: 评论次数： 阅读次数： 本文字数： 1.9k

想必现在的这个时候，很多人在难过，也有很多人在开心吧，至于为什么呢，因为今天又是一年一度的激动人心的考研查分日，依稀记得当时的自己查分的时候好像有点过于淡定了～不晓得大家上完岸后有什么打算，就我本人而言，虽然目前就读的这所学校在我国还是很有名的，地段也好（上海），有些排名甚至能进个前三，但是不知道为啥，总感觉我在这是浪费时间。就比如现在，本人正坐在学校的图书馆，刷了一小会题后，发现自己是真的垃圾，于是乎，转过来写点另类的垃圾。。。读研还是蛮苦的，不是累，是心里承担的太重了（话有点多了，开始正题^-^）

今天想记录下的题目类型是有关于去重的问题，其实呢，去重的思路有很多，使用场景也不少，比如说有链表的去重啦，数组的去重啦，很多很多，或许有人会说，这不简单嘛，由于set自身就具有去重的属性，那我直接把要去重的都丢到set中不就好了，确实，这也是一种方法，今天我想讲的是利用双指针来进行去重～

问题介绍

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。

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

示例：

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

思路

对于这道题来说，需要注意，如果nums的大小是小于等于2的话，其实是可以直接返回的；我们只需要注意当nums.length>2的情况。

需要注意到的特性：

如果nums中的第三个数等于第一个数，就表示第三个数是不被需要的，因为该数的个数已经为2了。因此可以设置两个指针slow与fast，指向第三个数（因为可以根据nums[fast] == nums[slow-2]，这里可以看出，slow指向的其实是已经处理完的序列的后一位数字）。

以示例来说明算法过程：

  • slow与fast均指向nums[2] = 1，判断nums[fast] == nums[slow - 2]，即1 == 0（否），所以slow所指的数是需要留下的，因此，slow与fast同时后移；
  • slow与fast均指向nums[3] = 1，nums[fast] != nums[slow - 2]，所以继续后移；
  • slow与fast均指向nums[4] = 1， nums[fast] = nums[slow - 2] = 1，所以slow所指的数字不需要被留下，因此，slow不需要移动，fast往后移动；
  • slow指向nums[4] = 1，fast指向nums[5] = 1，继续将fast往后移，直到fast所指的值不等于nums[slow - 2] = 1；
  • fast指向nums[6] = 2，nums[fast] != nums[slow - 2]，所以将fast所指的数复制到slow所指的值，并两者同时后移（0,0,1,1,2,1,2,3,3）；
  • fast指向nums[7] = 3，slow指向nums[5] = 1，nums[slow - 2] = 1 != nums[fast]，所以继续复制（0,0,1,1,2,3,2,3,3），fast与slow同时后移；
  • fast指向nums[8] = 3，slow指向nums[6] = 2，nums[slow - 2] = 2 != nums[fast]，所以继续复制（0,0,1,1,2,3,3,3,3），fast与slow同时后移；
  • fast == nums.length，所以遍历结束，slow所指的值为处理完序列的下一个数字，因此就是有效序列的长度，返回即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int removeDuplicates(int[] nums) {
    if(nums.length <= 2){
        return nums.length;
    }

    int slow = 2;
    int fast = 2;
    while (fast < nums.length){
        if(nums[slow - 2] != nums[fast]){
            nums[slow++] = nums[fast];
        }
        fast++;
    }
    return slow;
}

本题相关拓展

这道题是将重复的数字可以保留两个，其实这种双指针的方法可以拓展保留k个，只需要将代码中的2变为k，即可；这种思路在去重中其实还是比较常见，奈何博主记性不好，总是在做到类似题时想不起来这种方法。其实在链表中也是可以使用的哟，只是需要适当修改下。

结束

好啦，我还是太懒了，写这么点东西，硬是拖到了现在（2022/02/21 20.07，外面也已经黑了）。。手机真的没啥玩的，QQ里没啥朋友聊，微信也只是看看课程群（不知道为啥，现在我竟然还会对课程群中的新消息有所期待～看来我是太无聊了。。）

无聊的我，待会也得回寝室去了，，今天又是无所事事的一天，我的研究生生涯又浪费了一天，24小时，1440分钟，86400秒，唉～

番剧嘛，最近已经在追了，还没完结，完结后再推荐给大家（额，，其实是写给以后的自己看的，看看那时的自己到底有多傻～），白白啦～