class Solution:
#time O(N) space O(N)
def findDuplicates(self, nums: List[int]) -> List[int]:
d = {}
res = []
for num in nums:
if num not in d:
d[num] = True
else:
res.append(num)
return res
follow up, note here repeated elements only appear twice, so the potential problem result has repteated numbers is avoided. reference
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
#time O(N) space O(1)
# main idea: based on restriction 1<= a[i]t<=n, 0<=i ,= n-1, use input array as a hash to store numbers seen before
n = len(nums)
res = []
for i in range(n):
x = abs(nums[i])-1
if nums[x] >= 0: # 0 <= nums[i]-1 <= n-1
nums[x] = abs(nums[x])*-1
else:
res.append(abs(nums[i]))
return res
for elements that repeated more than twice, need to use nums[num%size] to keep i in nums[i] not change while add size value at position num%size each time visited same num
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
#time O(2N) space O(1)
res = []
size = len(nums)
for num in nums:
nums[num%size] += size
for i in range(len(nums)):
if nums[i] >= size*2:
res.append(i)
print('size',size)
return res