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.这个题由于不允许使用额外空间，可以使用一个小技巧，对于数组中的元素nums[i]，把nums[nums[i] - 1]标记为相应负数，然后便利一遍数组，对于所有正数nums[i]，说明i + 1不存在。这个方法太诡异了，一般正常人类不太容易想到。

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if(nums == null || nums.length == 0)
            return res;

        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                if(nums[nums[i] - 1] > 0)
                    nums[nums[i] - 1] = -nums[nums[i] - 1];
            } else {
                if(nums[-nums[i] - 1] > 0)
                    nums[-nums[i] - 1] = -nums[-nums[i] - 1];
            }
        }

        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0)
                res.add(i + 1);
        }

        return res;
    }
}

2.正常人类一般回想到这个方法，把数组里的数放到相应的位置上，nums[i]应该是i + 1，对于不满足这个条件的，就是数组中缺失的数字，一些小技巧自行体会

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if(nums == null || nums.length == 0)
            return res;

        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == i + 1)
                continue;

            while(i < nums.length && nums[i] != i + 1 && nums[nums[i] - 1] != nums[i])
                swap(nums, i, nums[i] - 1);
        }

        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != i + 1)
                res.add(i + 1);
        }

        return res;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}