刷题之旅从数组类型的题目开始。第二十道题目是找到所有数组中消失的数字，对应leetcode的题号为448。

image

题目描述

对应leetcode的题号为448。

给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。

找到所有在 [1, n] 范围之间没有出现在数组中的数字。

您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

示例:

1
2
3
4
5
输入:
[4,3,2,7,8,2,3,1]

输出:
[5,6]

解题思路

一个比较简单的思路是用Set来去重，然后一一去找不存在的那个数。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        Set<Integer> set = new HashSet<>();
        for(int i=0;i<nums.length;i++){
            set.add(nums[i]);
        }
        for(int num=1;num<=nums.length;num++){
            if(!set.contains(num)){
                res.add(num);
            }
        }
        return res;
    }
}

此方法需要遍历两次数组，时间复杂度显然是O(n)级别(HashSet是基于散列表实现的，元素没有顺序；add、remove、contains方法的时间复杂度为O(1))，空间复杂度也显然是O(n)级别。执行结果：

1
2
执行用时 :34 ms, 在所有 Java 提交中击败了12.12%的用户
内存消耗 :52.8 MB, 在所有 Java 提交中击败了78.32%的用户

还可以用一个额外的标记数组来实现，即遍历原数组，然后将遍历的数字，对应到标记数组的索引处置为1，这样最后为0的元素就是原数组不存在的数字。不过题目要求不使用额外空间，如何来实现呢？

因为数组还是特殊的数组，是指定范围内的一串数字，中间有缺失的，也有重复的，那么对于这种类型的数组，我们还是可以利用数组索引来做。比如对于数字1，那么我们就在索引为(1-1)的地方做个标记表示这个数字存在；对于数字7，就在(7-1)的地方做个标记表示这个数字存在。那么可以很容易想到，对于某个不存在的数字比如5，那么对应(5-1)的地方一定是没有标记的，就很容易被找出来了。按照这个思想，我们就可以找到不用额外空间的解题思路。

以[4,3,2,7,8,2,3,1]为例，我们遍历数字，将其索引位置的数字置为负数。比如这里的4，那么我就将(4-1)处的数字置为相反数，即[4,3,2,-7,8,2,3,1]，第二步是3，那么数组变成[4,3,-2,-7,8,2,3,1]，第三步是2，数组变成[4,-3,-2,-7,8,2,3,1]；第四步是7，数组变成[4,-3,-2,-7,8,2,-3,1]；第五步是8，数组变成[4,-3,-2,-7,8,2,-3,-1]；第六步是2，这个时候是关键，因为2之前出现过并且已经将索引(2-1)的地方置为相反数了，此时不需要再取相反数；第七步是-3，这个时候也是关键，我们取的实际上还是3，即绝对值，然后发现索引(3-1)处已经是负数了就不去相反数；最后的-1也是同理。

所以为什么这里取相反数，实际上就是因为我们既要用负数来标记，也需要可以取绝对值从而得到原数组中的原来的值来继续判断，因此相反数是最合适的一个选择了。时间复杂度明显是O(n)，空间复杂度为O(1)。

提交代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import java.util.*;
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if(nums.length == 0){
            return res;
        }
        for(int i=0;i<nums.length;i++){
            //根据元素的绝对值找到对应的数组索引下标，注意要减一，因为数字是从1开始，而索引是从0开始
            int index = Math.abs(nums[i])-1;
            //如果发现索引处的元素大于零就取相反数，否则就不要再动了
            if(nums[index] > 0){
                nums[index] = nums[index] * (-1);
            }
        }
        //上面走完以后，只要出现过的数字，那么对应的索引一定是负数；反之为正数的说明为不存在的数字，挑出来即可
        for(int i=0;i<nums.length;i++){
            if(nums[i] > 0){
                res.add(i+1);
            }
        }
        return res;
    }
}
1
2
执行用时 :9 ms, 在所有 Java 提交中击败了48.07%的用户
内存消耗 :48.5 MB, 在所有 Java 提交中击败了90.51%的用户