leetcode第80题：删除有序数组的重复项（||）
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
说明：
为什么返回数值是整数，但输出的答案是数组呢？
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {print(nums[i]);
}
示例 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 <= nums.length <= 3 * 104-104 <= nums[i] <= 104nums已按升序排列
步骤 1：问题分析
题目性质：
给定一个升序数组 nums，需要原地删除重复出现超过两次的元素，确保每个元素最多出现两次。返回处理后数组的新长度，并在数组的前部存储符合条件的元素。
输入条件：
- 数组
nums长度为1 <= nums.length <= 30,000。 - 数组元素范围为
-10^4 <= nums[i] <= 10^4，并且已按升序排列。
输出条件：
- 函数应返回新数组的长度。
- 在函数内修改输入数组，并使其前部保存符合条件的元素。
边界条件：
- 数组为空时，返回
0。 - 数组中没有重复元素或每个元素最多出现两次时，直接返回数组长度。
问题抽象：
- 保留每个元素最多出现两次，并且修改后的数组仍然保持有序。
步骤 2：算法分解与设计思路
为了高效解决这个问题，我们可以采用双指针的技巧。该方法通过两个指针来同时遍历和修改数组：
- 快指针（
i）： 用来遍历整个数组，检查每一个元素。 - 慢指针（
j）： 用来更新数组，确保符合条件的元素最多出现两次。
具体步骤如下：
- 初始化： 定义慢指针
j = 1，并从第二个元素（i = 2）开始检查，前两个元素直接保留（因为每个元素最多出现两次）。 - 遍历数组：
- 从
i = 2开始，检查nums[i]是否与nums[j-1]相等。如果不相等，说明当前元素可以被保留，将其赋值给nums[j+1]，同时增加j。 - 如果相等，则跳过该元素（因为它已经出现超过两次）。
- 从
- 结束条件： 当快指针
i遍历完数组时，慢指针j+1就是处理后的数组新长度。
算法复杂度分析：
- 时间复杂度：
O(n)，其中n是数组长度。由于我们只遍历一次数组，时间复杂度是线性的。 - 空间复杂度：
O(1)，因为我们没有使用额外的空间，所有操作都是在原数组上完成的。
步骤 3：C++ 代码实现
步骤 4：优化和启发
这个问题启发我们在解决重复数据时，可以通过双指针或滑动窗口的技巧来降低空间复杂度。特别是在处理有序数组或流式数据时，双指针能有效减少不必要的遍历或额外存储。
此外，这种技巧广泛用于需要原地修改数组的场景，特别适合内存敏感的应用场合。
算法优化：
- 算法已经达到 O(n) 的最优时间复杂度，空间复杂度为 O(1)，无需进一步优化。
- 在大规模数据集的场景中，该算法具有较好的表现，能够处理几十万甚至上百万的元素。
步骤 5：实际应用场景
应用场景：数据清理与去重
在实际生活中，类似的算法广泛应用于数据清理和去重操作，例如：
- 金融数据：在交易数据中去除多次重复的无效交易记录，保留有限次的合法交易。
- 电商平台：在用户行为记录中，清理用户重复点击的商品数据，保留两次点击用于分析购买意图。
示例：电商平台中的用户行为去重 在电商平台的用户行为数据分析中，我们经常遇到用户短时间内多次点击同一个商品。这些点击行为如果过多，会影响用户兴趣的分析。因此我们可以使用类似的双指针算法，去除超过两次的重复点击，保留用户前两次点击记录，从而更加精准地分析用户的兴趣偏好。