题目要求
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]区间中的整数没有出现？
思路和代码
首先可以想到用另一个临时数组来记录每个元素出现的次数，则出现次数为零次的元素在数组中没有出现。代码如下：
public List<Integer> findDisappearedNumbers(int[] nums) { int[] temp = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) { temp[nums[i]]++; } List<Integer> result = new ArrayList<>(); for (int i = 1; i < temp.length; i++) { if (temp[i] == 0) { result.add(i); } } return result; }但是这个实现违背了O(1)的空间复杂度（这里结果集不视为额外空间）。因此如何才能避免使用临时数组呢？其实我们可以利用原数组中元素相互调换的方式，将其转化为一个新的有序的数组。即从最左边开始，每遇到一个元素，就将其防止到元素的目标位置上，如在第0位上遇到元素i，则将位置i-1上的元素和位置0上的元素进行交换，并在此判断新的元素是否需要交换。如果当前元素无需进行交换，则指针右移一位。无需进行的场景是指当前元素已经出现在目标位置上了。
public List<Integer> findDisappearedNumbers(int[] nums) { int index = 0; while(index < nums.length) { if(nums[index] == nums[nums[index]-1]) { nums[nums[index]-1] = nums[index]; index++; }else{ int tmp = nums[index]; nums[index] = nums[tmp-1]; nums[tmp-1] = tmp; } } List<Integer> result = new ArrayList<Integer>(); for(int i = 0 ; i < nums.length ; i++) { if(nums[i] != i+1) { result.add(i+1); } } return result; }