数组中重复的数据

🎯 问题描述（来源于LeetCode）

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 最多两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间（不包括存储输出所需的空间）的算法解决此问题。

💻 代码实现

初始思路

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        a=sorted(nums)
        ans=[]
        l=len(nums)
        x=a[0]
        for i in range(1,l):
            if a[i]==x:
                ans.append(x)
            x=a[i]
        return ans

但时间复杂度是$O(Nlog(N))$
原因是Python 的 sorted() 函数使用 Timsort 算法：

• Timsort 是归并排序和插入排序的混合算法
• 稳定排序（相等元素的相对顺序不变）
• 时间复杂度：平均和最坏情况都是 O(n log n)
  所以我们只需要优化排序算法就行。但优化排序会引进新的额外空间。所以说使用负数标记法（观看dominator的题解）：

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        ans=[]
        l=len(nums)
        for i in nums:
            idx=abs(i)-1
            if nums[idx]>0:
                nums[idx]=-nums[idx]
            else:
                ans.append(abs(i))
        return ans

📊 性能分析

提交结果

• 运行时间：19ms击败97.02%
• 内存消耗：26.56MB击败67.03%

复杂度验证

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$