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.
給定整數(shù)數(shù)組，其中元素a[i]滿足1 ≤ a[i] ≤ n (n 為數(shù)組大小)，一些元素出現(xiàn)兩次，其他的出現(xiàn)一次。
找出所有范圍在[1,n]之間且未在數(shù)組中的元素。
請(qǐng)勿使用額外的空間，且在線性時(shí)間內(nèi)完成?？杉俣ǚ祷氐牧斜聿凰阍陬~外空間內(nèi)。

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

思路：
利用hash思想，將數(shù)字和位置進(jìn)行聯(lián)系，利用位置x的數(shù)字正負(fù)表示數(shù)字x是否出現(xiàn)過(guò)。這種方法將改變輸入數(shù)組。

public class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            int val=Math.abs(nums[i])-1;
            if(nums[val]>0) nums[val]=-nums[val];
        }
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0) res.add(i+1);
        }
        return res;
    }
}

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res=[]
        for i in range(len(nums)):
            val = abs(nums[i])-1
            if nums[val]>0: nums[val]=-nums[val]
        for i in range(len(nums)):
            if nums[i]>0:res.extend([i+1])
        return res