1、前言

2、思路

如果使用桶排序的思路，那么避免不了使用 O(n) 的额外空间，虽然时间复杂度是 O(n)。

题目要求不使用额外空间，那么只能在原数组上做改动。由题目可知，数组中的每个数其实就相当于一个 index，我们改变 (index - 1) % nums.length 下标的数，将它加上 nums.length。后续再遍历原数组，如果数组中的数字小于等于 nums.length，那么说明该下标在数组中不存在，加入 list 即可。

3、代码

public class Q448_FindDisappearedNumbers {

    public List<Integer> findDisappearedNumbers(int[] nums) {
        if(nums == null || nums.length == 0){
            return new ArrayList<>();
        }

        int[] res = new int[nums.length + 1];
        for(int i = 0; i < nums.length; i++){
            int index = nums[i];
            res[index]++;
        }

        List<Integer> list = new ArrayList<>();
        for (int i = 1; i < res.length; i++) {
            if(res[i] == 0){
                list.add(res[i]);
            }
        }

        return list;
    }

    public List<Integer> findDisappearedNumbers2(int[] nums) {
        if(nums == null || nums.length == 0){
            return new ArrayList<>();
        }

        for (int i = 0; i < nums.length; i++) {
            int index = (nums[i] - 1) % nums.length;
            nums[index] = nums[index] + nums.length;
        }

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] <= nums.length){
                list.add(i + 1);
            }
        }

        return list;
    }

    public static void main(String[] args) {
        new Q448_FindDisappearedNumbers().findDisappearedNumbers2(new int[]{4,3,2,7,8,2,3,1});
    }
}