1、题目描述

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。

• 返回 k 。

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

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按 非严格递增 排列

2、解题思路：快慢指针法

由于数组是已排序的，重复元素一定相邻。可以通过快慢指针原地修改数组：

1. 慢指针（i）：指向当前已去重部分的最后一个位置。

2. 快指针（j）：遍历数组，寻找与 nums[i] 不同的元素。

关键步骤：

1. 初始化 i=0, j=1（因为第一个元素无需比较）。

2. 遍历数组：

   • 如果 nums[i] != nums[j]，说明 nums[j] 是新元素，将其复制到 i+1 的位置，然后移动 i 和 j。

   • 如果相等，则只移动 j（跳过重复项）。

3. 最终返回 i+1（去重后的长度）。

package other;

import org.junit.Test;

public class example{
    @Test
    public void test() {
        int[] nums = new int[]{0,1,2,2,3,3,3,4};
        System.out.println("双指针："+removeDuplicates (nums));
    }

    public int removeDuplicates (int[] nums) {
        int len = nums.length;
        if (len == 0) return 0;  // 空数组直接返回0
        int i = 0, j = 1;        // 初始化快慢指针
        while (j < len) {
            if (nums[i] != nums[j]) {  // 发现新元素
                nums[i + 1] = nums[j]; // 将新元素放到i+1位置
                i++;                   // 慢指针前移
                j++;                   // 快指针前移
            } else {                   // 重复元素
                j++;                   // 只移动快指针
            }
        }
        return i + 1;  // 新长度 = 慢指针位置 + 1
    }
}

3、复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组。

• 空间复杂度：O(1)，原地修改，未使用额外空间。

4、边界条件处理

1. 空数组：直接返回 0。

2. 无重复数组：如 [1,2,3]，直接返回原数组长度。

3. 全重复数组：如 [1,1,1]，返回 1（仅保留第一个元素）。

5、为什么返回 i + 1？

• i 始终指向去重部分的最后一个位置，而数组长度需要从1开始计数（类似长度 = 最后一个索引 + 1）。