leetCode 448. 找到所有数组中消失的数字

给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

第一种时间复杂度为O(2n)解法：

假设有一个从1~n的数字，新建一个数组长度为给定数组两倍的数组，然后拼接到后面循环处理，把数值存储到list中，记录第一个数组存储到list最后的位置，然后从这个位置分隔list，剩下的list的值就是结果

public List<Integer> findDisappearedNumbers(int[] nums) {
if (nums == null) {
return null;
}
int length = nums.length;
int[] maxNums = new int[2 * length];
//从1开始
int start = 1;
int bucket = 0;
List<Integer> list = new ArrayList<>();
for (int i = 0; i < maxNums.length; i++) {
if (i < length && !list.contains(nums[i])) {
list.add(nums[i]);
bucket++;
}
if (i >= length) {
if(!list.contains(start)){
list.add(start);
}
start++;
}
}
list = list.subList(bucket, list.size());

return list;

}

正确解法：

/**
 * 1.其实就是两个数组比较 另一个隐藏的数据就是1~给定数组的长度
 * 两个数组合并成一个  隐藏的数组拼接到后面  但此时时间复杂度为O(2n)
 * 2.可以将对应的数字nums[i]交换到对应数字的索引处  就是数字4应该交换到数组中的索引为3的位置处
 * 数组从0开始 所以和数组中数字-1的索引的位置的数字比较  数组从1开始，所以可以这样做，无需考虑交换时数组越界。
 *
 * @param nums
 * @return
 */
public List<Integer> findDisappearedNumbers(int[] nums) {
    if (nums == null) {
        return null;
    }
    int length = nums.length;
    List<Integer> list = new ArrayList<>();

    int temp;
    for (int i = 0; i < length; i++) {
        if (nums[i]!=nums[nums[i]-1]){
            temp = nums[nums[i]-1];
            nums[nums[i]-1] = nums[i];
            nums[i] = temp;
            i--;
        }
    }
    System.out.println(Arrays.toString(nums));
    for (int i = 0; i < length; i++) {
        if(nums[i]!= (i+1)){
            list.add(i+1);
        }
    }

    list.stream().forEach(num -> {
        System.out.println("num:" + num);
    });

    return list;

}