原题

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]

题意与思路

这道题是说，给我们一个数组，数组长度为 n，数组里面的每一个元素都是在

[1,n]的区间里的数字，里面有一些数字会出现多次，也就意味着有一些数字会没有，请我们找出那些缺失的数字。

一开始是想排序？先排序，然后在从头到尾遍历，但是有一些数字出现两次，不太好写判断条件。然后注意到所有的数字都一定是在 1 - n 范围的，那么，可以使用一个新的数组来标记这些数，哪些存在哪些不存在。

比如说，示例中，数组 [4,3,2,7,8,2,3,1]，第一个元素是 4，那么我们就用新数组 arr[4-1] 标记这个元素存在。也就是对于原数组中的元素 a，在新的数组 arr 中，标记 arr[a-1]= 1 来表示它存在。最后再遍历一下标记数组，那些空缺的数字，也就是我们需要的答案。

代码如下：

public List<Integer> findDisappearedNumbers(int[] nums) {int[] data = new int[nums.length];

    for (int i : nums) {data[i - 1] = 1;
    }

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

    for (int i = 0; i < data.length; i++) {if (data[i] == 0) {ret.add(i + 1);
        }
    }

    return ret;
}

时间复杂度可以一眼看出就是 O(2n)

当然，还可以改进一下这个算法，不用创建新的数组来做标记，如果只使用原来的数组，如何做标记呢？

如果使用原来的数组，需要一个很重要的问题：如果第一个数为 3，就意味着要去标记 data[3 – 1]的位置，但是 data[3 – 1]里面的数被破坏了，后面再遍历到它的时候怎么办呢？

也就是，如何同时标记一个数的位置，又不能破坏原有的数。

广大的劳动人民总是有无穷的智慧的：我们可以将要标记的数转为负数，如果是负数，就说明是被标记了（这个位置代表的数存在），同时也可以将负数转换回原来的数。

看看代码是怎么实现的呢:D

public List<Integer> findDisappearedNumbers(int[] nums) {for (int i = 0; i < nums.length; i++) {int index = Math.abs(nums[i]) - 1; // 先得到 index
        if (nums[index] > 0) { // 如果那个位置上的数 > 0
            nums[index] = -nums[index]; // 就标记它
        }
    }

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

    for (int i = 0; i < nums.length; i++) {if (nums[i] >= 0) { // 只要是大于 0 的数，就说明是没有的数
            ret.add(i + 1);
        }
    }

    return ret;
}

这样就通过原数组解决了问题~