题目
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]
难度
Medium
方法
因为1=<a[i]<=n，那么0<=a[i]-1<=n-1，因此可以将a[i]-1作为index。如果a[i]有2个，那么a[i]-1会出现2次。当a[i]第一次出现时，将a[a[i]-1]置为负值。将i++，如果a[a[i]-1]为负数的时候，表示a[i]之前一定出现过。
由于a[i]会被置为负数，因此a[a[i]-1]需要用a[abs(a[i])-1]
python代码
class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
duplicates = []
for i in range(len(nums)):
index = abs(nums[i])-1
if nums[index] < 0:
duplicates.append(index+1)
else:
nums[index] = -nums[index]
return duplicates
assert Solution().findDuplicates([4,3,2,7,8,2,3,1]) == [2,3]
assert Solution().findDuplicates([10,2,5,10,9,1,1,4,3,7]) == [10,1]
