11-03 02:41 阅读 105

关注

算法分析（三）：删除排序数组中的重复项

前言

• 这是一道运用到双指针的经典题目，双指针我一直用的不太好，通过这道题巩固一下基础

• 题目网址：leetcode-cn.com/problems/re…

双指针解法

• 这道题的暴力解法我都不想说了，就是遍历一遍然后将数组中重复的删除，但是你要循环两次并且你还要消耗大量的空间，所以我们需要想到其他的办法，就用一次循环解决

• 首先有个前提，只是一个有序数组，意思是他已将把数组排好序了，这就简单了，那重复的数字基本会在一起，所以我们开始开动脑经想一想

• 第一步我们需要对比两个相邻的数字是不是重复的吧

• 第二步如果不同步我们就比对下一个吧，因为是有序的，所以现在不相等，那以后也不会相等，所以我们一起移到下一步

• 第三步，继续比对，突然发现，两个相等了怎么办？正常的想法就是把相同的删除对吧，但是我不想删除，太消耗内存，那怎么办？我们可以让 J 指针指向下一个节点，I 不动，因为我不确定下一个是不是也跟 I 一样。

• 第四步，比对发现，不一样，那这个时候怎么做呢？聪明的你肯定想到了，把 I 移到下一个数组，并且把相同的值改成现在 J 的值，为什么怎么做呢，这么做的好处是什么呢？别急我们全部做完再看

• 第五步我们都做完了，来看看什么效果，就像下图一样，后面的 3 和 4 提前了，I 指针之前的数字都是不重复的，所以我们没有改变数组这个麻烦的举动就完成了对于重复数字的剔除是不是很神奇，这就是双指针的作用。

• 废话不多说上代码：

class Solution {     public int removeDuplicates(int[] nums) {      //慢指针         int i = 0;         //数组长度         int l = nums.length;         //循环遍历         for(int j=1;j<l;j++){          //当两个不相等的时候，双指针一起往前走             if(nums[i]!=nums[j]){                 i++;                 nums[i] = nums[j];             }         }         //返回数组长度，因为开始是从0开始的，所以需要+1         return i+1;     } } 复制代码

总结

双指针的做法远远不止于此，这道题还是比较好理解的，并且更为简单直观的表示了双指针的作用。

作者：程序胖
链接：https://juejin.cn/post/7026144514234384414