一道简单的数组题目：删除排序数组中的重复项

小灰灰 2022-02-16 08:42 208阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

题目来源于 LeetCode 第 26 号问题：删除排序数组中的重复项。题目难度为 Easy，目前通过率为 43.9%。

### 题目描述 ###

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

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

### 题目解析 ###

使用快慢指针来记录遍历的坐标。

*  开始时这两个指针都指向第一个数字
 *  如果两个指针指的数字相同，则快指针向前走一步
 *  如果不同，则两个指针都向前走一步
 *  当快指针走完整个数组后，慢指针当前的坐标加1就是数组中不同数字的个数

### 动画描述 ###

![640?wx\_fmt=gif][640_wx_fmt_gif] 动画描述

### 代码实现 ###

class Solution {
         
    public:
        int removeDuplicates(vector<int>& nums) {
        
            if (nums.empty()) return 0;
            int pre = 0, cur = 0, n = nums.size();
            while (cur < n) {
        
                if (nums[pre] == nums[cur]){
        
                  cur++;  
                } else{
        
                    ++pre;
                    nums[pre] = nums[cur];
                    cur++;
                } 
            }
            return pre + 1;
        }
    };

**推荐阅读**

[拜托，面试官别问我「布隆」了][Link 1]

[数据结构与算法：三十张图弄懂「图的两种遍历方式」][Link 2]

[昨天，终于拿到了腾讯 offer][offer]

[几道和「二叉树」有关的算法面试题][Link 3]

[几道和散列（哈希）表有关的面试题][Link 4]

[一道看完答案你会觉得很沙雕的「动态规划算法题」][Link 5]

[几道和「堆栈、队列」有关的面试算法题][Link 6]

[链表算法面试问题？看我就够了！][Link 7]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

欢迎关注![640?wx\_fmt=png][640_wx_fmt_png]

[640_wx_fmt_jpeg]: /images/20220216/74d0a26c2c184e8f934c8743458da534.png
[640_wx_fmt_gif]: /images/20220216/36efef8ebaea4fd78e6e2603d39ca9b8.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485011&idx=1&sn=a3031a3d3ad033e44439d42d72753e16&chksm=fa0e69d2cd79e0c45b1eb017c65b60662890f67ec70ef44e92ef7f5cddfc313ea6ab353952f4&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485076&idx=1&sn=ba747d1efd4c009da83681a6bb4ff549&chksm=fa0e6915cd79e003249e9ee045d09a174b0e5aff2a6ecd807e10fd01bfbc1a37da688eb51637&scene=21#wechat_redirect
[offer]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485001&idx=1&sn=cdcebef70aaabcafa3403c2dd51bdfb7&chksm=fa0e69c8cd79e0de12ece3a9e48430099c429aff816cc3a9e40035192dc07a864864888d1078&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484985&idx=1&sn=93343d355abf36c77a361c9931cbe2d1&chksm=fa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484977&idx=1&sn=f4a6148480555e3cca83231ac1df8d02&chksm=fa0e69b0cd79e0a686e31c547fc783eb9663d9fe19cc95ecd524e9f8f7e0d4a168945f8755e5&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 7]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 1]: /images/20220216/1b5ab51bb2e249819e3075fa1fe77116.png
[640_wx_fmt_png]: /images/20220216/652693875a6c45c2b6a4f5e741c0be20.png