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]

Note

和之前那道题目类似，这个题目找的是不存在的

把见过的数写成负数，同样利用数字值当作数组下标，再遍历是正数的话就是不存在的

Code

public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> ret = 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) {
            ret.add(i+1);
        }
    }
    return ret;
}