LC 0442 [M] Find All Duplicates in an Array - ALawliet/algorithms GitHub Wiki
def find_all_duplicates(nums):
i = 0
while i < len(nums):
j = nums[i] - 1
if nums[i] != nums[j]:
nums[i], nums[j] = nums[j], nums[i]
else:
i += 1
duplicateNumbers = []
for i in range(len(nums)):
if nums[i] != i + 1:
duplicateNumbers.append(nums[i])
return duplicateNumbers
Notice that if an element x occurs just once in the array, the value at index abs(x)-1 becomes negative and remains so for all of the iterations that follow.
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
res = []
for x in nums:
if nums[abs(x)-1] < 0:
res.append(abs(x))
else:
nums[abs(x)-1] *= -1
return res