刷题之旅从数组类型的题目开始。第十七道题目是存在缺失数字，对应leetcode的题号为268。

image

题目描述

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。

示例 1:

1
2
输入: [3,0,1]
输出: 2

示例 2:

1
2
输入: [9,6,4,2,3,5,7,0,1]
输出: 8

解题思路

首先这道题目一定要先明确数组的定义，这个数组很特别，是[0,1,2…n]这种数组，虽然是乱序的，但是数组一旦排序后就是很紧凑的逐一增加的数组，只不过中间一定少一个元素，我们需要找出来。

那么显然，常规思路是对数组进行排序，然后逐一比较相邻的两个数只差是否为1，也可以用索引下标去判断是否存在：

1
2
3
4
5
6
7
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
    if(nums[i] != i){
        return i;
    }
}
return nums.length;

或者也可以用map来做，首先全部装进map中，然后根据数组的特性，遍历i=0到i=nums.length，如果其中遍历不到的数字，就是我们要返回的不存在的数字。

1
2
3
4
5
6
7
Set<Integer> set = new HashSet<>();
for(int i = 0; i < nums.length; i++) set.add(nums[i]);   
for(int i = 0; i <= nums.length; i++)
    if(!set.contains(i)){
       return i;
    }
return -1;

不过这么特殊的数组，一定是有特殊的解法的，仔细想想，以

1
2
输入: [4，3，0，1]
输出: 2

为例，其索引是[0,1,2,3]，那么我们可以根据异或的思想来做：

1
2
1 ^ 1 = 0
0 ^ 1 = 1

那么[4,3,0,1]和[0,1,2,3]做异或，其实可以分解为：3 ^ 3，0 ^ 0，1 ^ 1，我们只需要想办法把4给异或掉，那么就剩下了2，那么结果就是2了（下面主要还是考虑正常情况，如果出现的数组为[0,1,2,3]这种不缺的，那么程序会返回4，这点可以根据情况去斟酌改变，不过不影响核心思想，不必纠结）。

对于[4,3,0,1]这个数组，我们第一步就用nums.length去和4做抵消。因为数组中最大的数字按照题意必然就是n。

好了，此时其他所有的n-1个数都互相抵消了，自然就剩下缺失的那个数字了，再举个例子：

1
2
输入: [9,6,4,2,3,5,7,0,1]
输出: 8

数组为[9,6,4,2,3,5,7,0,1]，索引数组为[0,1,2,3,4,5,6,7,8,9]，那么第一步是9 ^ 9=0，然后1，2，3，4，5，6，7都可以找到对应的索引异或掉，最终就剩下8了。

提交代码

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int missingNumber(int[] nums) {
        //如果遇到0-n都存在的情况，这里就直接返回n+1这个数字即可，因为这种情况题目没有说明如果返回
        int res = nums.length;
        for(int i=0;i<nums.length;i++){
            res ^= nums[i];
            res ^= i;
        }
        return res;
    }
}
1
2
执行用时 :1 ms, 在所有 Java 提交中击败了91.92%的用户
内存消耗 :39.6 MB, 在所有 Java 提交中击败了96.09%的用户

还有一种方法是加减，其实思想跟异或是一样的思路。