LeetCode每日一题: 26. 删除有序数组中的重复项

本是古典何须时尚 2022-11-11 06:14 187阅读 0赞

> 微信公众号：**Java随笔录**  
> 关注可了解更多Java相关的技术分享。问题或建议，欢迎公众号留言！

### 文章目录 ###

*   *   *  题目
         *  题目大意
         *  解题思路
         *  代码
         *  执行结果
         *  公众号

### 题目 ###

*  [https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/][https_leetcode-cn.com_problems_remove-duplicates-from-sorted-array]

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

不要使用额外的数组空间，你必须在原地修改输入数组并在使用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。不需要考虑数组中超出新长度后面的元素。

### 题目大意 ###

给定一个有序数组nums，对数组中的元素进行去重，使得原数组中的每个元素只有一个。最后返回去重以后数组的⻓度值。

### 解题思路 ###

这里数组的删除并不是真的删除，只是将删除的元素移动到数组后面的空间内，然后返回数组实际剩余的元素个数，OJ最终判断题目的时候会读取数组剩余个数的元素进行输出。

主要的问题就在于原地处理，最容易想到的方法就是暴力枚举，但是时间表现肯定很差。这时候双指针就可以派上用场了！双指针的方法在挺多时候都很实用，能够带来很不错的效果，后续的题目中还会遇到。

针对这道题目的主要思路就是，设置两个指针  i i i 和  j j j，如果  i = j i = j i=j，我们就增加  j j j 以跳过重复项，否则将  n u m s \[ j \] nums\[j\] nums\[j\] 的值复制到  n u m s \[ i + 1 \] nums\[i + 1\] nums\[i\+1\]，然后递增  i i i，重复上述过程。

*  时间复杂度： O ( n ) O(n) O(n)
 *  空间复杂度： O ( 1 ) O(1) O(1)

### 代码 ###

public int removeDuplicates(int[] nums) { 
        int len = nums.length;
        if (len <=1 )
            return len;
        int left, right;
        for (left = 0, right = 1; right < len; right++) { 
            if (nums[left] != nums[right]) { 
                nums[++left] = nums[right];
            }
        }
        return left + 1;
    }

### 执行结果 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pfX01heA_size_16_color_FFFFFF_t_70_pic_center]

### 公众号 ###

*  关注公众号，即时接收关于Java的技术分享！

![20210207183855124.JPG][]

[https_leetcode-cn.com_problems_remove-duplicates-from-sorted-array]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pfX01heA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/35fef62b53bd4868a25c8827758aefbd.png
[20210207183855124.JPG]: /images/20221022/54cbe6c4a1084e73807e8739fcea3c05.png