448. 找到所有数组中消失的数字 (opens new window)

1.鸽巢原理+原地哈希

分析：遍历两次数组。

• 第一轮遍历：将数组中每个元素放到索引下标为index=num[ i ]的位置中，填入前如果原先该位置的元素和索引不匹配，则循环重复上述操作，直到当前位置的值和索引相匹配。每次结束轮次i的递归填充时，最开始的起点元素num[ i ]要么等于 i (相当于递归时绕了一个环)，要么不等于 i 。
• 第二轮遍历：检查数组每个位置上的数和索引是否匹配，如果不匹配则说明该位置即为消失的数字。

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            int index=nums[i]-1;
            while(nums[index]!=index+1){
                int temp=nums[index];
                nums[index]=index+1;
                index=temp-1;
            }
        }

        for(int i=0;i<nums.length;i++){
            if(nums[i]!=i+1) res.add(i+1);
        }
        return res;
    }
}