[LeetCode]442. Find All Duplicat

题目

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]