268. 缺失数字

Posted on | In
Words count in article: 789 | Reading time ≈ 3

题目

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

示例1：

1
2
3
输入: [3,0,1]
输出: 2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例2：

1
2
3
输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例3：

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

示例4：

1
2
3
输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

提示：

  • n == nums.length
  • 1 <= n <= 104
  • 0 <= nums[i] <= n
  • nums 中的所有数字都 独一无二

进阶：

你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?

解法

解法一：

一个0-n的n个数列，每个数字只出现一个，只缺失了一个数字。用0-n这n+1和数字的和减去0-n这n个数字的和，差就是缺失的数字了。

Java

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int missingNumber(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        int ssum = 0;
        for (int i = 0;i <= nums.length;i++) {
        	ssum += i;
        }
        
        return ssum - sum;
    }
}

解法二：

使用额外数组（不符合题目要求）

使用一个长为n+1的数组，如果某个位置上的数字出现了，则该位置对应的值置为1。最后遍历该数字，找到为0的位置，就是缺失的数字。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
public int missingNumber(int[] nums) {
		int[] numss = new int[nums.length + 1];
		for (int i = 0;i < nums.length;i++) {
			numss[nums[i]] = 1;
		}
		
		for (int i = 0;i < numss.length;i++) {
			if (numss[i] == 0) {
				return i;
			}
		}
		return -1;
	}

解法三：

排序

对原数组进行排序，然后扫描该数组，得到缺失的值即可。

这里需要对首尾两处的值做特殊处理

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int missingNumber(int[] nums) {
		Arrays.sort(nums);
        
        // 判断 n 是否出现在末位
        if (nums[nums.length - 1] != nums.length) {
            return nums.length;
        } else if (nums[0] != 0) {
            // 判断 0 是否出现在首位
            return 0;
        }

		for (int i = 0;i < nums.length;i++) {
			if (i != nums[i]) {
				return i;
			}
		}
		return -1;
	}

解法四：

使用HashSet

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> numSet = new HashSet<Integer>();
        for (int num : nums) numSet.add(num);

        int expectedNumCount = nums.length + 1;
        for (int number = 0; number < expectedNumCount; number++) {
            if (!numSet.contains(number)) {
                return number;
            }
        }
        return -1;
    }
}

解法五：

异或位运算

数组是从0到n中有一个缺失，那么根据异或的特性，在遍历这个数据的时候，同时异或index和nums[index]的话，那些出现两次的数字就会消失，最后只剩下出现一次的缺失数字。

Java

1
2
3
4
5
6
7
8
public int missingNumber(int[] nums) {
    	// 初始化为n，因为循环中i无法到达n，只能到达n-1
		int result = nums.length;
		for (int i = 0;i < nums.length;i++) {
			result ^= i ^ nums[i];
		}
		return result;
	}
0%