leetcode第二十六题:删去有序数组的重复项

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

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

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

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

示例 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 已按 非严格递增 排列

步骤1：问题性质分析

• 问题类型：本题属于数组处理与去重问题。
• 输入条件：
  • 一个已经 非严格递增排列 的数组 nums（可以有重复元素）。
  • nums.length 范围：1 <= nums.length <= 3 * 10^4。
  • nums 的元素值范围：-10^4 <= nums[i] <= 10^4。
• 输出条件：
  • 返回去重后的新长度 k，并确保数组 nums 的前 k 个元素是唯一的，且顺序与原数组一致。
  • 数组中超过 k 个位置的元素无需考虑。
• 限制：
  • 必须原地修改数组，不能使用额外空间。

边界条件：

1. 如果数组 nums 为空（虽然输入约束不会出现这种情况），直接返回 0。
2. 如果数组没有重复元素，直接返回数组的长度 k = nums.size()。
3. 如果数组所有元素都相同，返回 1，因为所有元素去重后只会剩下一个。

步骤2：算法分解和分析

我们可以使用双指针法来解决这个问题，时间复杂度为 O(n)，空间复杂度为 O(1)。这种算法在本题非常高效，适合处理大规模数据。

双指针法步骤：

• 设定两个指针：

  1. slow 指针，用于标记不重复元素的存储位置。
  2. fast 指针，用于扫描整个数组。

• 算法逻辑：

  1. 初始时，slow = 0，fast = 1。
  2. 遍历数组 nums，如果 nums[fast] != nums[slow]，说明遇到了新的唯一元素：
     • 增加 slow 指针并更新 nums[slow] = nums[fast]。
  3. 如果 nums[fast] == nums[slow]，则跳过该元素，fast 继续前进。

• 时间复杂度：

  • 双指针每个元素最多访问一次，因此时间复杂度为 O(n)。

• 空间复杂度：

  • 只使用常量级别的额外空间，空间复杂度为 O(1)。

详细步骤：

1. 初始化 slow 和 fast 指针。
2. 使用 fast 遍历数组，每当遇到与 slow 不同的元素时，slow 增加并更新值。
3. 最终返回 slow + 1，即唯一元素的数量。

步骤3：C++代码实现

步骤4：算法的启发

通过解决此问题，我们可以从以下几方面获得启发：

1. 双指针技术：双指针是一种高效的遍历和处理数组的方法，尤其适合处理排序好的数组以及类似的连续数据结构。这种技术能显著提高算法的效率。
2. 原地修改：在大规模数据集处理时，减少额外的空间消耗是一个关键的优化点，尤其在实际生产环境中，当内存有限时，原地修改的算法更加高效。
3. 时间复杂度的优化：在需要线性扫描问题时，双指针法通过尽可能减少遍历的次数，有助于控制时间复杂度为 O(n)。

步骤5：实际生活中的应用

这个算法能够在实际生活中起到非常重要的作用，尤其是处理去重和排序的问题。常见应用场景包括：

• 物流优化：在物流行业，运送物品时可能会遇到大量重复的订单或货物，去重算法可以帮助优化配送计划，确保只运输不同的物品。

  • 实际例子：某个仓库每天接收到多个订单，但其中有许多是重复订单。使用类似的算法去重后，可以减少运输车辆的出行次数，提升运输效率，并节省成本。

• 金融数据去重：在金融领域，投资组合、股票交易数据等常常需要去除重复的历史记录，以进行后续的分析和预测。

  • 实际例子：某金融公司需要分析过去一年股票交易的历史数据，但这些数据中包含许多重复的记录。使用去重算法可以有效简化数据集，减少计算时间，提高预测模型的准确性。