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]

Solution:

数组长度为n，数组中元素的取值范围为[1, n]�，数组index范围为[0, n - 1]。也就是说如果数组元素没有重复，那么对于每个元素k，都对应一个index k-1.

因此我们可以利用这个性质，将出现的元素所对应的index上面的元素置负，用来表示该index所对应的元素存在（将nums[index] = - nums[index], 表示index + 1 这个数是存在的）。遍历整个数组对每个元素进行这个操作之后，再遍历一遍数组，如果某个index上的元素nums[index] 非负，则说明该index所对应的元素(index + 1)没有出现过，则将(index + 1)加入要返回的List。

// import java.util.*;

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

        List<Integer> result = new ArrayList<>();

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

        return result;
    }
}