找到所有数组中消失的数字

leetCode–448（找到所有数组中消失的数字）

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

示例 1：

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

示例 2：

输入：nums = [1,1]
输出：[2]

解法一：自己：借助额外的数组

代码为：

遍历数组，将数组中的值，放入新数组所对应值下标的位置。再遍历数组，哪个下标没有值，说明哪个数没在数组中，加入到链表中。

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        List<Integer> list = new ArrayList<>();
        int res[] = new int[n+1];
        for (int i = 0;i<n;i++){
            if (res[nums[i]]==0) {
                res[nums[i]] = nums[i];
            }else continue;
        }
        for (int i = 1;i<res.length;i++){
            if (res[i]==0){
                list.add(i);
            }
        }
        return list;
    }
}

解法二：不适用额外数组

遍历数组中的元素，将元素值所对应下标的位置元素+n。

再遍历一遍数组，如果小于等于n。说明该坐标位置没有被加n，也就是所遍历的元素中没有这个坐标数、也就是没有这个元素。

代码为：

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        List<Integer> list = new ArrayList<>();
        for (int i = 0;i<n;i++){
            //这个 %n 是为了当执行某个元素时数组已经改变了，所以%n 可以恢复为原来的值
            int x = (nums[i] - 1) % n;
            nums[x] = nums[x] + n;
        }
        for (int i = 0;i<n;i++){
            if (nums[i]<=n){
                list.add(i+1);
            }
        }
        return list;
    }
}