題目
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
方法
因?yàn)?code>1=<a[i]<=n都办，那么0<=a[i]-1<=n-1，因此可以將a[i]-1作為index混埠。如果a[i]有2個(gè)哄芜，那么a[i]-1會(huì)出現(xiàn)2次。當(dāng)a[i]第一次出現(xiàn)時(shí)贮聂，將a[a[i]-1]置為負(fù)值靠柑。將i++，如果a[a[i]-1]為負(fù)數(shù)的時(shí)候吓懈，表示a[i]之前一定出現(xiàn)過歼冰。
由于a[i]會(huì)被置為負(fù)數(shù)，因此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]
