数组去重算法分析：保留最多k个重复元素

2025-04-15

问题描述

给定一个有序数组，删除重复出现的元素，使每个元素最多出现k次（原题中k=2），返回删除后数组的新长度。(leetcode 80)

三种解法分析

解法1：双指针（基于间隔比较）

public int removeDuplicates(int[] nums) {
   int n = nums.length;
   if(n <= 2){
    return n;
   }
   int slow = 2;
   for(int fast = 2; fast < n ; fast++){
    if(nums[fast] != nums[slow - 2]){
        nums[slow] = nums[fast];
        slow++;
    }
   }
   return slow;
}

算法思路：

使用快慢指针，slow指向待插入位置，fast用于遍历数组
slow初始为2（因为前两个元素一定保留）
核心判断：比较当前元素(nums[fast])与往前第k个位置的元素(nums[slow-k])
如果不相等，则说明当前元素可以插入（重复次数没有超过k次）
slow最终指向新数组长度

执行流程示例：假设数组 [1,1,1,2,2,3]，保留最多2个重复元素：

slow = 2, fast = 2: nums[2]=1, nums[0]=1，相等，跳过
slow = 2, fast = 3: nums[3]=2, nums[0]=1，不相等，保留：[1,1,2]，slow=3
slow = 3, fast = 4: nums[4]=2, nums[1]=1，不相等，保留：[1,1,2,2]，slow=4
slow = 4, fast = 5: nums[5]=3, nums[2]=2，不相等，保留：[1,1,2,2,3]，slow=5
返回 slow = 5

时间复杂度：O(n)，只需遍历一次数组 空间复杂度：O(1)，只使用常量额外空间

解法2：双指针（基于条件判断）

public int removeDuplicates(int[] nums) {
    int n = nums.length;
    if(n <= 2){
        return n;
    }
    int slow = 1;
    //分两种情况处理：1.不相等 2.相等
    for(int fast = 2; fast < n ; fast++){
        if(nums[fast] != nums[slow]){
            slow++;
            nums[slow] = nums[fast];
        }else{
            if(nums[fast] != nums[slow - 1]){
                slow++;
                nums[slow] = nums[fast];
            }
        }
    }
    return ++slow;
}

算法思路：

slow从1开始（因为第一个元素必定保留）
分两种情况：
1. 当前元素与slow指向的元素不同，直接添加
2. 当前元素与slow指向的元素相同，还需检查是否与slow-1指向的元素不同（确保最多有2个重复元素）
最后返回slow+1（因为slow是从0开始的索引）

执行流程示例：假设数组 [1,1,1,2,2,3]，保留最多2个重复元素：

slow = 1, fast = 2: nums[2]=1, nums[1]=1相等，且nums[2]=1, nums[0]=1相等，跳过
slow = 1, fast = 3: nums[3]=2, nums[1]=1不相等，保留：[1,1,2]，slow=2
slow = 2, fast = 4: nums[4]=2, nums[2]=2相等，但nums[4]=2, nums[1]=1不相等，保留：[1,1,2,2]，slow=3
slow = 3, fast = 5: nums[5]=3, nums[3]=2不相等，保留：[1,1,2,2,3]，slow=4
返回 slow+1 = 5

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

解法3：计数法

public int removeDuplicates(int[] nums) {
   int n = nums.length;
   if(n <= 2) return n;
   int slow = 1;
   int count = 1;
   for(int fast = 1; fast < n; fast++){
    if(nums[fast] == nums[fast-1]){
        count++;
    }else{
        count = 1;
    }
    if(count <= 2){
        nums[slow] = nums[fast];
        slow++;
    }
   }
   return slow;
}

算法思路：

使用count变量跟踪当前元素连续出现的次数
遍历数组时，如果当前元素与前一个元素相同，count++；否则重置count=1
只有当count≤2时，才将当前元素保留在结果数组中
slow最终指向新数组的长度

执行流程示例：假设数组 [1,1,1,2,2,3]，保留最多2个重复元素：

slow = 1, fast = 1: nums[1]=1, nums[0]=1，相等，count=2，保留：[1,1]，slow=2
slow = 2, fast = 2: nums[2]=1, nums[1]=1，相等，count=3，count>2，跳过
slow = 2, fast = 3: nums[3]=2, nums[2]=1，不相等，count=1，保留：[1,1,2]，slow=3
slow = 3, fast = 4: nums[4]=2, nums[3]=2，相等，count=2，保留：[1,1,2,2]，slow=4
slow = 4, fast = 5: nums[5]=3, nums[4]=2，不相等，count=1，保留：[1,1,2,2,3]，slow=5
返回 slow = 5

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

扩展：保留最多k个重复元素

解法1的扩展

public int removeDuplicates(int[] nums, int k) {
   int n = nums.length;
   if(n <= k){
    return n;
   }
   int slow = k;
   for(int fast = k; fast < n ; fast++){
    if(nums[fast] != nums[slow - k]){
        nums[slow] = nums[fast];
        slow++;
    }
   }
   return slow;
}

修改点：

将初始的 slow 从 2 改为 k
将比较条件 nums[slow - 2] 改为 nums[slow - k]
边界条件从 n <= 2 改为 n <= k

思路解析：这种方法的核心是确保任何元素最多出现k次。通过比较当前元素与”往前数第k个位置”的元素是否相同，来决定是否接受当前元素。如果它们不同，说明当前元素与之前保留的元素中相同值不超过k-1个，可以接受；如果相同，说明如果再接受当前元素，相同值就会达到k+1个，所以要跳过。

解法2的扩展

public int removeDuplicates(int[] nums, int k) {
    int n = nums.length;
    if(n <= k){
        return n;
    }
    int slow = k - 1;
    
    for(int fast = k; fast < n; fast++){
        // 检查当前元素是否可以添加
        boolean canAdd = false;
        
        if(nums[fast] != nums[slow]){
            // 不同元素直接添加
            canAdd = true;
        } else {
            // 需要检查是否已有k个重复元素
            int count = 1;
            for(int i = 1; i < k; i++){
                if(slow - i >= 0 && nums[slow] == nums[slow - i]){
                    count++;
                }
            }
            if(count < k){
                canAdd = true;
            }
        }
        
        if(canAdd){
            slow++;
            nums[slow] = nums[fast];
        }
    }
    return slow + 1;
}

修改点：

初始 slow 设置为 k-1
添加了一个辅助函数来计算已有的重复元素数量
只有当重复次数小于k时才添加当前元素

思路解析：解法2的泛化比较复杂，需要通过向前查找来确定已经保留了多少个相同的元素。当遇到与slow指向的元素相同的元素时，需要检查之前是否已经保留了k个该元素，如果小于k个，则可以添加；否则跳过。

解法3的扩展

public int removeDuplicates(int[] nums, int k) {
   int n = nums.length;
   if(n <= k) return n;
   int slow = 1;
   int count = 1;
   for(int fast = 1; fast < n; fast++){
    if(nums[fast] == nums[fast-1]){
        count++;
    }else{
        count = 1;
    }
    if(count <= k){
        nums[slow] = nums[fast];
        slow++;
    }
   }
   return slow;
}

修改点：

只需将条件 count <= 2 改为 count <= k

思路解析：解法3是最容易扩展到k个重复元素的方案。它显式地跟踪每个元素的出现次数，当遇到新元素时重置计数器，只有当当前元素的出现次数不超过k时才保留它。

总结与比较

解法1（基于间隔比较）:
- 优点：实现简洁，直接通过比较与”往前第k个”元素的关系来决定
- 缺点：隐式地假设数组已经排序，对于某些输入可能不直观
解法2（基于条件判断）:
- 优点：逻辑清晰，分情况讨论
- 缺点：扩展到k个重复元素时实现较复杂，需要额外循环来计数
解法3（计数法）:
- 优点：最直观，显式跟踪每个元素的出现次数，易于理解和扩展
- 缺点：需要额外的计数变量

对于保留k个重复元素的需求，解法3（计数法）是最推荐的方案，因为它:

实现简单，只需修改一个常量
逻辑清晰，显式跟踪元素出现次数
代码结构容易理解和维护

最终选择：如果需要保留k个重复元素，解法3是最佳选择，因为它清晰明了且易于扩展；如果固定保留2个重复元素，解法1提供了最简洁的实现。