给定一个数组a[]，长度为n，保证1<=a[i]<=n,找出1-n中所有未出现的数字，不使用额外空间且时间复杂度为O(n).
如果可以使用额外空间，我们会使用一块额外空间来记录某一个数字是否出现过，遍历一遍a来更新额外空间状态，然后遍历额外空间来获得未出现的数字。现在不允许使用额外空间，我们可以不可以直接在数组上来保存状态？可以这样做，假设数组长度为n，我们发现a[0]=3，那么说明3出现一次，由于数组下标是0~n-1，所以我们更新下标为2的值来表示3出现一次，怎么更新呢？直接让a[2]+n这样的话每次使用数组都要%n得到实际的值，代码如下
public class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { List<Integer> result = new ArrayList<>(); int n = nums.length; // 完成此次循环后，nums[i]代表i+1出现的次数 // 通过和将值和n比较，如果大于n说明有出现过i+1的值 // 每次发现一个值，就－1然后和%n防止已经出现多次 for (int i = 0; i != n; ++i) { nums[(nums[i] - 1) % n] += n; } for (int i = 0; i != n; ++i) { if (nums[i] <= n) { result.add(i + 1); } } return result; } }