代码训练LeetCode(11)删除有序数组中的重复项II

代码训练(11)LeetCode之删除有序数组中的重复项II

Author: Once Day Date: 2024年3月14日

漫漫长路，才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

• 80. 删除有序数组中的重复项 II - 力扣（LeetCode）
• 力扣 (LeetCode) 全球极客挚爱的技术成长平台

文章目录

• • • 代码训练(11)LeetCode之删除有序数组中的重复项II

1. 原题

比如对于[1, 1, 1, 2, 2, 3]，应该返回长度5，数组则变更为[1, 1, 2, 2, 3]。

2. 分析

给定一个有序数组 nums，你需要原地修改这个数组，去除那些出现超过两次的重复元素。这里的“原地”意味着你不能使用额外的数组结构来辅助完成这个任务；仅能使用有限的额外空间（O(1)），也就是说，除了几个变量以外，不得使用额外的空间资源。

由于数组已经有序，所以重复的元素一定是连续的。我们可以使用两个指针来解决这个问题：

1. i：慢指针，指向当前需要检查的位置。
2. j：快指针，遍历数组。

分析步骤：

1. 初始化两个指针 i = 2 和 j = 2（因为前两个元素最多保留两次，所以可以直接跳过）。
2. 遍历数组，从索引 2 开始，直到数组结束。
3. 如果 nums[j] 与 nums[i-2] 不同，说明 nums[j] 可以保留（因为这保证了最多只有两个重复元素）：
   • 把 nums[j] 的值赋给 nums[i]
   • 然后递增 i。
4. 无论元素是否相同，j 都需要递增，继续检查下一个元素。
5. 当 j 遍历完整个数组时，i 就是新数组的长度。

假设有数组 nums = [1,1,1,2,2,3]：

• 初始化 i 和 j 为 2。
• 当 j=2 时，nums[j] 与 nums[i-2] 都是 1，因此跳过。
• j 增加到 3，nums[j] 是 2，可以保留，所以 nums[i] = nums[j]，然后 i 和 j 都增加 1。
• 重复以上步骤直到 j 遍历完数组。
• 结果数组是 [1,1,2,2,3]，新数组长度为 5。

性能优化关键点：

• 尽量减少不必要的赋值操作，因为数组是有序的，所以当检测到不需要删除元素时，可以跳过赋值。
• 使用局部变量存储频繁访问的数组元素，减少数组索引操作以提高速度。

3. 代码实现

#include <stdio.h>

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize <= 2) {
        return numsSize;
    }

    int i = 2;
    for (int j = 2; j < numsSize; j++) {
        if (nums[j] != nums[i - 2]) {
            nums[i++] = nums[j];
        }
    }
    return i;
}

这段代码实现了一个函数 removeDuplicates，用于移除一个有序整数数组中出现的重复元素，但保留最多两次重复出现。函数的主要逻辑如下：

1. 函数接收两个参数：整数数组 nums 和数组的大小 numsSize。
2. 首先判断数组大小是否小于等于 2，如果是，则直接返回原始数组大小，因为不需要进行去重操作。
3. 初始化一个变量 i 为 2，表示去重后数组的当前位置。
4. 使用一个 for 循环遍历数组，从索引 2 开始到数组末尾。
5. 在循环内部，比较当前元素 nums[j] 与去重后数组的倒数第二个元素 nums[i - 2] 是否相等：
   • 如果不相等，说明当前元素出现次数不超过两次，将其复制到去重后数组的当前位置 nums[i]，并将 i 自增 1。
   • 如果相等，说明当前元素已经出现两次，不进行复制操作，直接继续循环。
6. 循环结束后，返回 i 的值，表示去重后数组的长度。

这个函数通过原地修改数组的方式，将重复出现超过两次的元素移除，保留最多两次重复出现的元素。最终返回去重后数组的长度。时间复杂度为 O(n)，空间复杂度为 O(1)。

运行结果如下(仅供参考):

4. 总结

这个问题考察了数组操作和双指针技巧的使用。这类问题在编程中相当常见，特别是在处理数据集或者优化存储空间时。