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:

1
2
3
4
5
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]

思路

Simple when using hashtable…..But not so easy when it comes to no extra space.

A very useful hint: When using python+hashtable to do word count, using Collection() function comes quite handy. The function can directly return a hashtable(python dict) with word statistics.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def findDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        resultdict = {}
        for i in nums:
            if resultdict.has_key(i):
                resultdict[i] += 1
            else:
                resultdict[i] = 1
        
        ans = []
        for i in resultdict:
            if (resultdict[i] == 2):
                ans.append(i)
                
        return ans

Hint: Take advantage of condition “1 ≤ a[i] ≤ n”
https://discuss.leetcode.com/topic/64979/python-o-n-time-o-1-space