Find All Numbers Disappeared in an Array

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:

Input:

[4,3,2,7,8,2,3,1]


Output:

[5,6]

题目大意：

给定一个整数数组，其中1 ≤ a[i] ≤ n (n = 数组长度)，一些元素出现两次，其他的出现一次。

寻找所有[1, n]中没有出现在数组中的元素。

可以不使用额外空间并在O(n)运行时间求解吗？你可以假设返回列表不算额外空间。

方法1： hashmap

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        hashmap = collections.Counter(nums)
        result = []
        for i in xrange(1,len(nums)+1):
            if i not in hashmap:
                result.append(i)
        return result

方法2正负号标记法：

对于每个数字nums[i]，如果其对应的nums[nums[i] - 1]是正数，我们就赋值为其相反数，如果已经是负数了，就不变了，那么最后我们只要把留下的正数对应的位置＋1然后加入结果res中即可，因为正数对应的元素没有被上一步骤标记过。

The basic idea is that we iterate through the input array and mark elements as negative usingnums[nums[i] -1] = -nums[nums[i]-1]. In this way all the numbers that we have seen will be marked as negative. In the second iteration, if a value is not marked as negative, it implies we have never seen that index before, so just add it to the return list.

The basic idea here is to label all appeared numbers in the array. Since we don't want to introduce extra space and given all numbers are positive(from 1 to n), negate the value in the corresponding position is one choice.

Complexity is O(n) Time and O(1) space.

注意：最后是正值的整数所在位置加一。

class Solution(object):
    def findDisappearedNumbers(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]
        for i in xrange(len(nums)):
            if nums[i] > 0:
                result.append(i+1)
        return result

简化 ：

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        for num in nums:
            if nums[abs(num)-1]>0:
                nums[abs(num)-1] = -nums[abs(num)-1]
        return [i+1 for i,n in enumerate(nums) if n>0]