跳转至

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

题目描述

原题

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

示例 1：

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

示例 2：

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

提示：

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n

**进阶：**你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。

题解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        //本题和剑指offer第3题很像
        //创建一个辅助数组 0的位置放1 1的位置放2 ...n-1的位置放n最后找到为0的数组
        int len = nums.length;
        int[] aux = new int[len];
        for(int i = 0;i < len ;i++){
            aux[nums[i]-1] = nums[i]; 
        }
        List<Integer> list = new ArrayList<>();
        for(int i = 0;i < len;i++){
            if(aux[i]==0){
                //获取为0的索引然后+1
                list.add(i+1);
            }
        }
        return list;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//官方解法，不创建新的数组，采用原地归并的方式
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        //找到当前x然后nums[x]+n
        //如果不存在某一个数，那么对应的nums[x]也不会+n
        //[4,3,2,7,8,2,3,1] len = 8第一个索引为4 那么nums[3]就会+8=15
        //3出现两次所以nums[2]位置会+2*8 = 18
        //依次遍历的到的最终结果[12, 19, 18, 15, 8, 2, 11, 9]
        //因为不存在5，6的值 对应的nums[4]和nums[5]也不会+8
        int n = nums.length;
        for (int num : nums) {
            int x = (num - 1) % n;
            nums[x] += n;
        }
        List<Integer> ret = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            if (nums[i] <= n) {
                ret.add(i + 1);
            }
        }
        return ret;
    }
}