26. 删除有序数组中的重复项【简单】

深碍√TFBOYSˉ_ 2022-10-08 05:40 157阅读 0赞

# 26. 删除有序数组中的重复项 【简单】 #

## 题目描述： ##

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

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

**说明:**

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以\*\*「引用」\*\*方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
    int len = removeDuplicates(nums);
    
    // 在函数里修改输入数组对于调用者是可见的。
    // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
    for (int i = 0; i < len; i++) { 
        print(nums[i]);
    }

**示例 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 。不需要考虑数组中超出新长度后面的元素。

**提示：**

>  *  0 <= nums.length <= 3 \*  1 0 4 10^4 104
>  *  \- 1 0 4 10^4 104 <= nums\[i\] <=  1 0 4 10^4 104
>  *  nums 已按升序排列

## JAVA方法： ##

思想：将不重复的数字，从0开始依次放置在数组头部，返回不重复数字的个数。程序内部会帮我们返回原数组的前n个元素（也就是我们整理好的，不重复的数字集）。

### 基本方法： ###

class Solution { 
        public int removeDuplicates(int[] nums) { 
    
             //判空
             if(nums.length==0||nums.length==1){ 
                 return nums.length;
             }
    
             //指向要插入的数组下标
             int n = 1;
             //循环判断与已有数字不同的，并放置到待插入数组下标内。
             for(int i = 1;i<nums.length;i++){ 
                 if(nums[i]!=nums[n-1]){ 
                    nums[n] = nums[i];
                    n++;
                 }
             }
             return n;
        }
    }

![在这里插入图片描述][20210620103636620.png]

### 双指针方法（快慢指针）： ###

改良：应用了快慢指针的思想，整理代码。

class Solution { 
        public int removeDuplicates(int[] nums) { 
    
             //判空
             if(nums.length==0||nums.length==1){ 
                 return nums.length;
             }
    
             //快指针
             int fast = 1;
             //慢指针
             int slow = 1;
             
             //快指针查找（不重复，待插入）的数字
             //慢指针定位待插入的位置
             while(fast<nums.length){ 
                 if(nums[fast]!=nums[fast-1]){ 
                     nums[slow] = nums[fast];
                     ++slow;
                 }
                 ++fast;
             }
    
             return slow;
        }
    }

![在这里插入图片描述][20210620104053640.png]

[20210620103636620.png]: /images/20221005/06b515c846524b0c8091ade7527eaae5.png
[20210620104053640.png]: /images/20221005/4d11df7ee84344a392c1ddf19353fd5e.png