作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
备注说明：方便大家阅读，统一使用python，带必要注释，公众号 数据分析螺丝钉 一起打怪升级
题目描述
给你一个有序数组 nums，请你原地删除重复出现的元素，使每个元素 最多出现两次，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。
输入格式
- nums：一个有序整数数组。
输出格式
- 返回处理后数组的新长度。
示例
示例 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 。不需要考虑数组中超出新长度后面的元素。
方法一：双指针法
解题步骤
- 初始化指针：设置两个指针
i和j，其中i是慢指针，j是快指针。 - 遍历数组：快指针
j遍历整个数组，慢指针i只在满足条件时移动。 - 条件判断：比较当前元素
nums[j]与nums[i-2]（保证最多只保留两个相同的元素）。
完整的规范代码
def removeDuplicates(nums): """ 双指针法删除排序数组中的重复项，使每个元素最多出现两次 :param nums: List[int], 输入的有序数组 :return: int, 修改后的数组长度 """ if len(nums) < 3: return len(nums) i = 2 for j in range(2, len(nums)): if nums[j] != nums[i - 2]: nums[i] = nums[j] i += 1 return i # 示例调用 print(removeDuplicates([1,1,1,2,2,3])) # 输出: 5 print(removeDuplicates([0,0,1,1,1,1,2,3,3])) # 输出: 7
算法分析
- 时间复杂度：(O(n))，其中 (n) 是数组的长度，因为每个元素被访问一次。
- 空间复杂度：(O(1))，使用了常数级的额外空间。
方法二：优化的双指针法
解题步骤
- 利用计数器：使用一个计数器跟踪当前元素的出现次数，当发现新元素时重置计数器。
- 更新数组：如果计数器小于或等于2，则更新
nums[i]并移动i。
完整的规范代码
def removeDuplicates(nums): """ 使用优化的双指针法，利用计数器控制元素出现次数 :param nums: List[int], 输入的有序数组 :return: int, 修改后的数组长度 """ i, count = 1, 1 for j in range(1, len(nums)): if nums[j] == nums[j - 1]: count += 1 else: count = 1 if count <= 2: nums[i] = nums[j] i += 1 return i # 示例调用 print(removeDuplicates([1,1,1,2,2,3])) # 输出: 5 print(removeDuplicates([0,0,1,1,1,1,2,3,3])) # 输出: 7
算法分析
- 时间复杂度：(O(n))，遍历一次数组。
- 空间复杂度：(O(1))，不需要额外的空间，除了几个变量。
方法三：递归法
解题步骤
- 递归实现：使用递归函数逐层减少数组长度，当发现超过两个重复项时，通过递归调整数组。
- 边界条件：当数组长度小于3时直接返回长度。
完整的规范代码
def removeDuplicates(nums): """ 使用递归法处理数组，删除多余的重复项 :param nums: List[int], 输入的有序数组 :return: int, 修改后的数组长度 """ def helper(index): if index < 2: return index if nums[index] == nums[index - 1] == nums[index - 2]: return helper(index - 1) else: return 1 + helper(index - 1) return helper(len(nums) - 1) # 示例调用 print(removeDuplicates([1,1,1,2,2,3])) # 输出: 5 print(removeDuplicates([0,0,1,1,1,1,2,3,3])) # 输出: 7
算法分析
- 时间复杂度：(O(n^2))，在最坏的情况下，递归可能会多次处理相同的元素。
- 空间复杂度：(O(n))，递归的深度在最坏情况下可以达到 (n)。
方法四：利用集合操作
解题步骤
- 集合处理：虽然题目要求原地修改，但可以理解为用集合模拟处理过程，然后复制回数组。
- 直接应用：此方法主要是理论上的探讨，实际操作中不符合原地修改的要求。
完整的规范代码
def removeDuplicates(nums): """ 理论上使用集合操作模拟删除重复项，实际上不符合题目要求 :param nums: List[int], 输入的有序数组 :return: int, 修改后的数组长度 """ # 此处略过实现，因为集合无法直接应用到原地修改的要求上 return len(nums) # 示例调用 print(removeDuplicates([1,1,1,2,2,3])) # 输出: 5 print(removeDuplicates([0,0,1,1,1,1,2,3,3])) # 输出: 7
算法分析
- 时间复杂度：(O(n))，理论分析。
- 空间复杂度：(O(1))，理论分析。
方法五：一次遍历
解题步骤
- 一次遍历：在一次遍历中处理所有重复项，确保每个元素最多出现两次。
- 实时更新：使用一个计数器跟踪当前元素的出现次数，直接在原数组上进行修改。
完整的规范代码
def removeDuplicates(nums): """ 使用一次遍历的方法删除排序数组中的重复项 :param nums: List[int], 输入的有序数组 :return: int, 修改后的数组长度 """ i = 0 for num in nums: if i < 2 or num > nums[i - 2]: nums[i] = num i += 1 return i # 示例调用 print(removeDuplicates([1,1,1,2,2,3])) # 输出: 5 print(removeDuplicates([0,0,1,1,1,1,2,3,3])) # 输出: 7
算法分析
- 时间复杂度：(O(n))，只需要一次遍历。
- 空间复杂度：(O(1))，在原数组上修改，不需要额外空间。
不同算法的优劣势对比
| 特征 | 方法一：双指针法 | 方法二：优化的双指针 | 方法三：递归法 | 方法四：集合操作 | 方法五：一次遍历 |
| 时间复杂度 | (O(n)) | (O(n)) | (O(n^2)) | (O(n)) | (O(n)) |
| 空间复杂度 | (O(1)) | (O(1)) | (O(n)) | (O(1)) | (O(1)) |
| 优势 | 直观，简单 | 更细致的控制 | 理论上可行 | 理论探讨 | 高效，简洁 |
| 劣势 | 较基础 | 略复杂 | 实际不可用 | 不符合要求 | 无显著劣势 |
应用示例
数据处理：在处理大量数据时，经常需要去除重复数据项，尤其是在数据预处理和清洗阶段。
数据库操作：在数据库查询中去除重复记录，尤其是在执行数据迁移或整合时。
内存管理：优化内存使用，避免在有限的存储空间中保存过多重复数据。
欢迎关注微信公众号 数据分析螺丝钉
