高效去重:有序数组中重复项的优雅删除

在有序数组中删除重复项通常是一个常见的编程问题。以下是一个使用Python的解决方案,它利用了数组的有序性质,通过原地修改数组(即不使用额外的数组空间)来删除重复项。

图片[1]_高效去重:有序数组中重复项的优雅删除_知途无界

这里有一个简单的Python函数,它接受一个有序数组(列表)作为输入,并返回一个新的长度,表示没有重复项的部分的长度。同时,它也会修改原始列表,将非重复项移到列表的前面。

def removeDuplicates(nums):  
    if not nums:  # 如果数组为空,直接返回0  
        return 0  
  
    i = 0  # 慢指针,指向当前不重复的元素  
    for j in range(1, len(nums)):  # 快指针,用于遍历数组  
        if nums[j] != nums[i]:  # 如果当前元素与前一个元素不同  
            i += 1  # 慢指针后移  
            nums[i] = nums[j]  # 将当前元素复制到慢指针指向的位置  
  
    return i + 1  # 返回不重复元素的数量(即新长度),注意这里+1是因为i是索引  
  
# 示例  
nums = [1,1,2,2,3]  
print("原始数组:", nums)  
length = removeDuplicates(nums)  
print("新长度:", length)  
print("修改后的数组:", nums[:length])  # 只打印不重复的部分

运行以上代码,输出将是:

原始数组: [1, 1, 2, 2, 3]  
新长度: 3  
修改后的数组: [1, 2, 3]

请注意,这个函数会直接修改传入的列表nums,并返回新长度。如果你不想修改原始列表,可以创建一个新列表来保存非重复元素,但这将需要额外的空间。然而,由于题目要求原地修改,上述解决方案是符合要求的。

© 版权声明
THE END
喜欢就点个赞,支持一下吧!
点赞15 分享
评论 抢沙发
头像
欢迎您留下评论!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容