LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】

简介: LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

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 。不需要考虑数组中超出新长度后面的元素。

方法一:双指针法

解题步骤
  1. 初始化指针:设置两个指针 ij,其中 i 是慢指针,j 是快指针。
  2. 遍历数组:快指针 j 遍历整个数组,慢指针 i 只在满足条件时移动。
  3. 条件判断:比较当前元素 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)),使用了常数级的额外空间。

方法二:优化的双指针法

解题步骤
  1. 利用计数器:使用一个计数器跟踪当前元素的出现次数,当发现新元素时重置计数器。
  2. 更新数组:如果计数器小于或等于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)),不需要额外的空间,除了几个变量。

方法三:递归法

解题步骤
  1. 递归实现:使用递归函数逐层减少数组长度,当发现超过两个重复项时,通过递归调整数组。
  2. 边界条件:当数组长度小于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)。

方法四:利用集合操作

解题步骤
  1. 集合处理:虽然题目要求原地修改,但可以理解为用集合模拟处理过程,然后复制回数组。
  2. 直接应用:此方法主要是理论上的探讨,实际操作中不符合原地修改的要求。
完整的规范代码
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)),理论分析。

方法五:一次遍历

解题步骤
  1. 一次遍历:在一次遍历中处理所有重复项,确保每个元素最多出现两次。
  2. 实时更新:使用一个计数器跟踪当前元素的出现次数,直接在原数组上进行修改。
完整的规范代码
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))
优势 直观,简单 更细致的控制 理论上可行 理论探讨 高效,简洁
劣势 较基础 略复杂 实际不可用 不符合要求 无显著劣势

应用示例

数据处理:在处理大量数据时,经常需要去除重复数据项,尤其是在数据预处理和清洗阶段。

数据库操作:在数据库查询中去除重复记录,尤其是在执行数据迁移或整合时。

内存管理:优化内存使用,避免在有限的存储空间中保存过多重复数据。



欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
18天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
15 3
|
24天前
|
缓存 Java 数据库连接
java面试题目 强引用、软引用、弱引用、幻象引用有什么区别?具体使用场景是什么?
【6月更文挑战第28天】在 Java 中,理解和正确使用各种引用类型(强引用、软引用、弱引用、幻象引用)对有效的内存管理和垃圾回收至关重要。下面我们详细解读这些引用类型的区别及其具体使用场景。
23 3
|
28天前
|
存储 算法 调度
【数据结构与算法】详解循环队列:基于数组实现高效存储与访问
【数据结构与算法】详解循环队列:基于数组实现高效存储与访问
|
13天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
22天前
|
机器学习/深度学习 存储 算法
数据结构与算法:数组的操作
数据结构与算法:数组的操作
|
26天前
|
开发框架 .NET
技术好文共享:面试题:找出数组中只出现一次的2个数(异或的巧妙应用)(出现3次)
技术好文共享:面试题:找出数组中只出现一次的2个数(异或的巧妙应用)(出现3次)
|
28天前
|
存储 算法 编译器
【数据结构与算法】使用数组实现栈:原理、步骤与应用
【数据结构与算法】使用数组实现栈:原理、步骤与应用
|
29天前
|
存储 算法 Java
Java数据结构与算法:线性数据结构之数组
Java数据结构与算法:线性数据结构之数组
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题