博客

一、题目描述

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

二、解题思路

这道题可以使用我的

74_数组中重复的数据

中的思路二，加n的方法。

下面通过分析来说明一下这个方法，还是先给出一个数组，下面两个是做对比用的。



第一步：遍历第一个元素4，4对应的索引(一定要注意这里不是在数组中实际的索引)4-1=3；索引3在数组中对应的值是7，将这个数加n，n是数组的长度等于8，7+8=15，将这个位置的数改成15（先别管为什么这么操作，往下看就行了）。



第二步：遍历第二个元素3，3对应的索引是2，索引2在数组中对应的值是2，将其加n：



第三步：遍历第三个元素10，我们通过上一步应该知道，不能直接找10对应的索引吧，这个10原来的数字是2，2对应的下标是2-1=1；那么怎么通过这个10也能找到这个下标1呢？这里有一个转换公式：

(nums[i]-1)%n

，代入来看看(10-1)%8=1，也得到了索引1，将索引1在数组中对应的值3也加n：

第四步：遍历第四个元素15，同第三步一样，这里得到的索引应该是6，将索引6在数组中对应的值加n:

第五步：比例第五个元素8，同理对应的索引是8-1=7；索引7在数组中的元素是1，将其加n：



第六步：遍历第六个元素2，2对应的索引是1，索引1在数组中对应的值是11，将其加n得19：



第七步：遍历第七个元素11，同第三步一样，原本元素值是3，它的索引2在数组中对应的值是10，然后加n：



第八步：比例第8个元素9，同第三步，它要找的索引是0，将索引0在数组中对应的值加n:



这是只要寻找数组中元素小于等于n的数即可，可见有8和2，他们对应的索引分别是4和5，索引加一就是我们要找的消失的数字。

二、代码演示

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        for (int i=0; i< nums.length; i++){
            //找索引的公式
            int index = (nums[i]-1)%n;
            //索引对应数组中的元素加n
            nums[index] += n;
        }

        List<Integer> res = new ArrayList<>();
        for (int i=0; i<n; i++){
            //加n后的数组中的元素判断
            if (nums[i]<=n){
                res.add(i+1);
            }
        }
        return res;
    }
}