Find All Duplicates in an Array

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]

题目大意：

给定一个整数数组，1 <= a[i] <= n (n = 数组长度)，某些元素出现两次，某些出现一次。寻找数组中所有出现两次的元素。你可以不使用额外空间并且在O(n)运行时间内完成题目吗？

解题思路：

方法1 hashmap

class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        hashmap=collections.Counter(nums)
        return [i for i in hashmap if hashmap[i]>1]

方法2 正负号标记法

when find a number i, flip the number at position i-1 to negative. if the number at position i-1 is already negative, i is the number that occurs twice.class

    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        result =[]
        for num in nums:
            if nums[abs(num)-1] > 0:
                nums[abs(num)-1] = -nums[abs(num)-1]
            else:
                result.append(abs(num))
        return result