最后更新于6年前
借鉴26. 删除排序数组中的重复项
先排序，然后一次遍历 O（lgn） + O（n）
由于数字范围与数组长度有关(1 ≤ a[i] ≤ n ),因此可以将元素值与元素下标联系起来(由于下标范围是0~n-1,因此还需要做一个偏移)。
遍历数组，将元素值作为下标(index)，用index访问数组，每次访问就将该元素置反（添负号），这样第二次访问为负的元素就是 重复项。
class Solution: def findDuplicates(self, nums: List[int]) -> List[int]: res = [] for i in range(len(nums)): index = abs(nums[i]) - 1 #数组元素值映射为下标 if nums[index] < 0: #第二次访问 res.append(index+1) nums[index] = -nums[index] #每次置反 return res
