【LeetCode Top 100】448. Find All Numbers Disappeared in an Array【Easy】【JAVA】

阳光穿透心脏的1/2处 2021-09-21 00:58 231阅读 0赞

## 1. 题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]

## 2. 题意 ##

题目很好理解，需要注意的是范围是`[1,n]`，跟数组下标范围`[0,n-1]`刚好相差了1。

## 3. 方法一 ##

### 3.1 思路 ###

由于数字范围刚好大于数组下标范围1，最简单的思路，构造一个大小为n的boolean类型的数组`boolean[] isContain`，`isContain[i]`代表数组中是否包含了数字`i+1`。从头到尾遍历整个数组，对每个值val，将`isContian[val-1]`置为`true`，即标记出现的值。再从头到尾遍历`isContain`数组，找出哪些下标为false，推断出哪些数字没有出现在\[1,n\]的范围中。  
该方法的时间复杂度为`O(n)`，需要遍历2次数组，空间复杂度为`O(n)`，为boolean数组的开销。

### 3.2 代码 ###

public List<Integer> findDisappearedNumbers(int[] nums) { 
            boolean[] isContain = new boolean[nums.length];
            for (int num : nums
                    ) { 
                isContain[num - 1] = true;
            }
            
            List<Integer> response = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) { 
                if (!isContain[i]) { 
                    response.add(i + 1);
                }
            }
            return response;
        }

### 3.3 运行结果 ###

![在这里插入图片描述][20191222210045775.png]

## 4. 方法二 ##

### 4.1 思路 ###

对于方法一，运行速度快，但没有实现空间复杂度为`O(1)`，接下来考虑保持时间复杂度不变`O(n)`，降低空间复杂度。  
考虑方法一，我们的空间开销是在boolean数组上，它的作用在于记录哪些值已经出现过了，因此我们考虑能否使原数组也有记录值是否出现的能力。联想到一个简单的方法，`正负值`，我们可以当某个值出现时，我们修改原数组的值的正负，来标记该值是否已经出现。  
例如对于`[3,3,2]`数组，我们从头遍历，第一个数字的绝对值为3，将3-1=`2`下标对应的值修改为负，原数组变为`[3,3,-2]`，对于第二个数，同样绝对值为3，将3-1=`2`下标对应的值修改为负，原数组为`[3,3,-2]`，遍历第三个数，绝对值为2，将2-1=`1`下标对应的值改为负，原数组为`[3,-3,-2]`，从头遍历数组，发现只有下标为0的数为正，即该数组中不包含0+1=`1`，不包含`1`这个数。

### 4.2 代码 ###

public List<Integer> findDisappearedNumbers1(int[] nums) { 
            for (int i = 0; i < nums.length; i++) { 
                int temp = Math.abs(nums[i]) - 1;
                if (nums[temp] > 0) { 
                    nums[temp] = -nums[temp];
                }
            }
            List<Integer> response = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) { 
                if (nums[i] > 0) { 
                    response.add(i + 1);
                }
            }
            return response;
        }

### 4.3 运行结果 ###

![在这里插入图片描述][20191222214326154.png]

## 5. 相关链接 ##

[本题代码的github链接][github]  
[其他 LeetCode 题目解析][LeetCode]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/4f987e95752240698db6fde8932a6032.png
[20191222210045775.png]: /images/20210920/e569575a95e045ab8b8daa91d712408b.png
[20191222214326154.png]: /images/20210920/89591313783847b3a3b3b5554a1cfb13.png
[github]: https://github.com/Parallelline1996/Leetcode/blob/master/Problems/src/main/java/page5/N448_FindAllNumbersDisappearedInAnArray.java
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html