Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example: 

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

思路

利用Python的set来解决问题。
实际上可以利用标记的方法来解决：
步骤：
[4,3,2,2] -> [4,3,2,-2]
[4,3,2,-2] -> [4,3,-2,-2]
[4,3,-2,-2] -> [4,-3,-2,-2]
此时标记完成，只有第一个元素没有被标记成为负数。
再找非负的元素，就是对应的没出现的元素了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        numset = set(nums)
        length = len(nums)
        result = []
        
        for i in range(1,length+1):
            result.append(i)
        
        resultset = set(result)
        final = resultset - numset
        result = list(final)
        
        return result