刷题之旅从数组类型的题目开始。第十七道题目是存在缺失数字,对应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%的用户

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