给你一个 非严格递增排列 的数组 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] <= 104nums已按 非严格递增 排列
步骤1：问题性质分析
- 问题类型：本题属于数组处理与去重问题。
- 输入条件：
- 一个已经 非严格递增排列 的数组
nums（可以有重复元素）。 nums.length范围：1 <= nums.length <= 3 * 10^4。nums的元素值范围：-10^4 <= nums[i] <= 10^4。
- 一个已经 非严格递增排列 的数组
- 输出条件：
- 返回去重后的新长度
k，并确保数组nums的前k个元素是唯一的，且顺序与原数组一致。 - 数组中超过
k个位置的元素无需考虑。
- 返回去重后的新长度
- 限制：
- 必须原地修改数组，不能使用额外空间。
边界条件：
- 如果数组
nums为空（虽然输入约束不会出现这种情况），直接返回0。 - 如果数组没有重复元素，直接返回数组的长度
k = nums.size()。 - 如果数组所有元素都相同，返回
1，因为所有元素去重后只会剩下一个。
步骤2：算法分解和分析
我们可以使用双指针法来解决这个问题，时间复杂度为 O(n)，空间复杂度为 O(1)。这种算法在本题非常高效，适合处理大规模数据。
双指针法步骤：
-
设定两个指针：
slow指针，用于标记不重复元素的存储位置。fast指针，用于扫描整个数组。
-
算法逻辑：
- 初始时，
slow = 0，fast = 1。 - 遍历数组
nums，如果nums[fast] != nums[slow]，说明遇到了新的唯一元素：- 增加
slow指针并更新nums[slow] = nums[fast]。
- 增加
- 如果
nums[fast] == nums[slow]，则跳过该元素，fast继续前进。
- 初始时，
-
时间复杂度：
- 双指针每个元素最多访问一次，因此时间复杂度为 O(n)。
-
空间复杂度：
- 只使用常量级别的额外空间，空间复杂度为 O(1)。
详细步骤：
- 初始化
slow和fast指针。 - 使用
fast遍历数组，每当遇到与slow不同的元素时，slow增加并更新值。 - 最终返回
slow + 1，即唯一元素的数量。
步骤3：C++代码实现
步骤4：算法的启发
通过解决此问题，我们可以从以下几方面获得启发：
- 双指针技术：双指针是一种高效的遍历和处理数组的方法，尤其适合处理排序好的数组以及类似的连续数据结构。这种技术能显著提高算法的效率。
- 原地修改：在大规模数据集处理时，减少额外的空间消耗是一个关键的优化点，尤其在实际生产环境中，当内存有限时，原地修改的算法更加高效。
- 时间复杂度的优化：在需要线性扫描问题时，双指针法通过尽可能减少遍历的次数，有助于控制时间复杂度为 O(n)。
步骤5：实际生活中的应用
这个算法能够在实际生活中起到非常重要的作用，尤其是处理去重和排序的问题。常见应用场景包括：
-
物流优化：在物流行业，运送物品时可能会遇到大量重复的订单或货物，去重算法可以帮助优化配送计划，确保只运输不同的物品。
- 实际例子：某个仓库每天接收到多个订单，但其中有许多是重复订单。使用类似的算法去重后，可以减少运输车辆的出行次数，提升运输效率，并节省成本。
-
金融数据去重：在金融领域，投资组合、股票交易数据等常常需要去除重复的历史记录，以进行后续的分析和预测。
- 实际例子：某金融公司需要分析过去一年股票交易的历史数据，但这些数据中包含许多重复的记录。使用去重算法可以有效简化数据集，减少计算时间，提高预测模型的准确性。
