26. 删除有序数组中的重复项

问题描述

给定一个非严格递增排列的整数数组 nums，原地删除重复出现的元素，使每个元素只出现一次，并返回删除后数组的新长度。要求：

1. 原地修改数组（空间复杂度 O(1)）
2. 保持元素相对顺序
3. 不需要考虑数组中超出新长度后面的元素

示例：

输入：nums = [1,1,2]
输出：2, nums = [1,2]（新长度后的元素不需要处理）

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]

算法思路：双指针（快慢指针）

1. 指针定义：

   • 慢指针 slow：指向下一个非重复元素应该放置的位置
   • 快指针 fast：遍历数组寻找新元素

2. 核心操作：

   • 当 fast 遇到与 slow 不同的元素时，将其复制到 slow+1 位置
   • 复制后 slow 前进一位（保证 slow 左侧全为无重复元素）

3. 过程本质：

   • slow 左侧：已处理的非重复元素（严格递增）
   • slow 与 fast 之间：被跳过的重复元素
   • fast 右侧：待处理区域

代码实现

class Solution {
    public int removeDuplicates(int[] nums) {
        // 空数组直接返回0
        if (nums.length == 0) return 0;
        
        int slow = 0;  // 慢指针（已处理区域的边界）
        
        // 快指针从1开始遍历
        for (int fast = 1; fast < nums.length; fast++) {
            // 发现新元素（非重复元素）
            if (nums[fast] != nums[slow]) {
                slow++;  // 慢指针前进
                nums[slow] = nums[fast];  // 复制新元素到正确位置
            }
            // 重复元素则跳过（快指针继续前进）
        }
        
        return slow + 1;  // 新长度 = 索引 + 1
    }
}

算法分析

• 时间复杂度：O(n)
  仅需遍历数组一次
• 空间复杂度：O(1)
  仅使用两个指针变量

算法过程

nums = [0,0,1,1,1,2,2,3,3,4] ：

1. 初始：slow=0, fast=1
nums[0]=0（已处理）
2. fast=1：0==0 → 跳过
3. fast=2：1≠0 → slow=1, nums[1]=1
4. fast=3：1==1 → 跳过
5. fast=4：1==1 → 跳过
6. fast=5：2≠1 → slow=2, nums[2]=2
7. fast=6：2==2 → 跳过
8. fast=7：3≠2 → slow=3, nums[3]=3
9. fast=8：3==3 → 跳过
10. fast=9：4≠3 → slow=4, nums[4]=4
11. 返回 slow+1=5（有效元素：[0,1,2,3,4]）

关键点

1. 有序数组特性：

   • 重复元素必然相邻 → 只需比较当前元素与前一个非重复元素
   • 非严格递增允许连续重复（如 [1,2,2,3]）

2. 指针移动规则：

   条件	操作
   nums[fast] == nums[slow]	跳过（快指针前进）
   nums[fast] != nums[slow]	慢指针前进后复制

3. 边界索引处理：

   • 慢指针起始位置0（首个元素无需比较）
   • 返回长度需 slow+1（索引→长度转换）

边界处理

边界情况	处理方式
空数组	返回0
单元素数组	直接返回1
全重复数组	返回1（如 [7,7,7] → [7]）
无重复数组	原样保留（如 [1,2,3]）
超大数组	O(n) 时间确保高效处理

测试用例

public static void main(String[] args) {
    Solution solution = new Solution();
    
    // 标准测试
    int[] nums1 = {0,0,1,1,1,2,2,3,3,4};
    int len1 = solution.removeDuplicates(nums1);
    System.out.println(len1 + ", " + Arrays.toString(Arrays.copyOf(nums1, len1)));
    // 输出：5, [0,1,2,3,4]
    
    // 全重复数组
    int[] nums2 = {7,7,7,7};
    int len2 = solution.removeDuplicates(nums2);
    System.out.println(len2 + ", " + Arrays.toString(Arrays.copyOf(nums2, len2)));
    // 输出：1, [7]
    
    // 无重复数组
    int[] nums3 = {1,2,3,4,5};
    int len3 = solution.removeDuplicates(nums3);
    System.out.println(len3 + ", " + Arrays.toString(Arrays.copyOf(nums3, len3)));
    // 输出：5, [1,2,3,4,5]
    
    // 空数组
    int[] nums4 = {};
    int len4 = solution.removeDuplicates(nums4);
    System.out.println(len4); // 0
    
    // 单元素数组
    int[] nums5 = {5};
    int len5 = solution.removeDuplicates(nums5);
    System.out.println(len5); // 1
}

常见问题

1. 为什么慢指针从0开始？
   首个元素必然是非重复序列的起点，无需比较直接保留。

2. 遇到重复元素时慢指针为何不移动？
   慢指针标识非重复序列的边界，遇到重复元素时该位置仍需被后续新元素填充。

3. 算法是否会改变非重复元素顺序？
   不会。每个新元素按原顺序被复制到慢指针位置，相对顺序严格保持。

4. 如何处理严格递增数组？
   算法同样适用（严格递增是非严格递增的特例）。

80. 删除有序数组中的重复项 II

问题描述

给定一个有序数组 nums，原地删除重复出现的元素，使得每个元素最多出现两次，返回删除后数组的新长度。要求：

• 必须在原地修改输入数组
• 使用 O(1) 额外空间

示例：

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前七个元素被修改为 0, 0, 1, 1, 2, 3, 3。不需要考虑数组中超出新长度后面的元素。

算法思路

双指针法（快慢指针）：

1. 核心思想：利用快指针 fast 扫描数组，慢指针 slow 标记有效位置
2. 关键判断：比较 fast 与 slow-2 位置的元素
   • 若不同 → 保留当前元素（复制到 slow 位置）
   • 若相同 → 跳过当前元素（已出现超过两次）
3. 边界处理：前两个元素无需判断（直接保留）

代码实现

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        // 处理长度小于等于2的情况（无需删除）
        if (n <= 2) return n;
        
        int slow = 2;  // 慢指针（从索引2开始）
        // 快指针遍历整个数组（从索引2开始）
        for (int fast = 2; fast < n; fast++) {
            /*
             * 关键判断：比较快指针元素与慢指针前两位元素
             * - 若 nums[fast] != nums[slow-2]：说明当前元素出现未超过两次
             * - 若相等：说明当前元素已出现两次（需跳过）
             */
            if (nums[fast] != nums[slow - 2]) {
                nums[slow] = nums[fast];  // 保留当前元素
                slow++;                   // 移动慢指针
            }
            // 若相等则跳过（快指针继续移动，慢指针不动）
        }
        return slow;  // 返回新数组长度
    }
}

算法分析

• 时间复杂度：O(n)
  快指针遍历数组一次，每个元素只处理一次。
• 空间复杂度：O(1)
  仅使用两个指针变量，无额外空间。

算法过程

nums = [1,1,1,2,2,3] ：

步骤	fast	nums[fast]	slow	比较 nums[slow-2]	操作	数组状态
初始	-	-	2	-	-	[1,1,1,2,2,3]
1	2	1	2	nums[0]=1 → 相等	跳过	[1,1,1,2,2,3]
2	3	2	2	nums[0]=1 → 不等	保留	[1,1,2,2,2,3]
3	4	2	3	nums[1]=1 → 不等	保留	[1,1,2,2,2,3]
4	5	3	4	nums[2]=2 → 不等	保留	[1,1,2,2,3,3]

结果：新长度 = 5，数组前5位 = [1,1,2,2,3]

测试用例

public static void main(String[] args) {
    Solution solution = new Solution();
    
    // 测试用例1：标准示例
    int[] nums1 = {1,1,1,2,2,3};
    System.out.println("Test 1: " + solution.removeDuplicates(nums1)); // 5
    
    // 测试用例2：全相同元素（超过两次）
    int[] nums2 = {0,0,0,0,0};
    System.out.println("Test 2: " + solution.removeDuplicates(nums2)); // 2
    
    // 测试用例3：无重复元素
    int[] nums3 = {1,2,3,4,5};
    System.out.println("Test 3: " + solution.removeDuplicates(nums3)); // 5
    
    // 测试用例4：每个元素恰好重复两次
    int[] nums4 = {1,1,2,2,3,3};
    System.out.println("Test 4: " + solution.removeDuplicates(nums4)); // 6
    
    // 测试用例5：空数组
    int[] nums5 = {};
    System.out.println("Test 5: " + solution.removeDuplicates(nums5)); // 0
}

关键点

1. 双指针分工：
   • 快指针 fast：扫描原数组
   • 慢指针 slow：标记新数组的写入位置
2. 核心逻辑：
   nums[fast] != nums[slow-2] 确保元素最多重复两次
3. 原地修改：
   直接在原数组覆盖，避免额外空间
4. 有序数组特性：
   重复元素必然连续，只需比较相邻位置

常见问题

1. 为什么比较 slow-2？
   因为要确保当前元素在保留部分中未出现两次（slow-2 是当前写入位置的前两个元素）。
2. 如何处理前两个元素？
   前两个元素无需判断（slow 从2开始），天然满足最多重复两次。
3. 快指针会覆盖未处理元素吗？
   不会。快指针始终领先/等于慢指针，覆盖位置的数据已被处理过。

此解法可扩展至保留 k 次重复：
只需将 slow-2 改为 slow-k，并添加长度校验（if (n <= k) return n;）