来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/missing-number/solution/que-shi-shu-zi-by-leetcode/

描述

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1]
输出: 2

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

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

题解

哈希表

常规做法，但需要使用268. 缺失数字(Missing Number) - 图1的空间复杂度

  1. class Solution {
  2.     public int missingNumber(int[] nums) {
  3.         Set<Integer> numSet = new HashSet<>();
  4.         for (int num : nums) {
  5.             numSet.add(num);
  6.         }
  8.         int expectedNumCount = nums.length + 1;
  9.         for (int number = 0; number < expectedNumCount; number++) {
  10.             if (!numSet.contains(number)) {
  11.                 return number;
  12.             }
  13.         }
  15.         return -1;
  16.     }
  17. }

复杂度分析

  • 时间复杂度：268. 缺失数字(Missing Number) - 图2。插入操作的时间复杂度都是268. 缺失数字(Missing Number) - 图3，一共插入了268. 缺失数字(Missing Number) - 图4个数，时间复杂度为268. 缺失数字(Missing Number) - 图5。集合的查询操作的时间复杂度同样是268. 缺失数字(Missing Number) - 图6，最多查询268. 缺失数字(Missing Number) - 图7次，时间复杂度为268. 缺失数字(Missing Number) - 图8，因此总的时间复杂度为268. 缺失数字(Missing Number) - 图9。

  • 空间复杂度：268. 缺失数字(Missing Number) - 图10。集合中会存储268. 缺失数字(Missing Number) - 图11个数，因此空间复杂度为268. 缺失数字(Missing Number) - 图12。

    位运算

    需要细细品~

    1. class Solution {
    2.   public int missingNumber(int[] nums) {
    3.       int res = nums.length;
    4.       for (int i = 0; i < nums.length; i++) {
    5.           res ^= i ^ nums[i];
    6.       }
    8.       return res;
    9.   }
    10. }

    复杂度分析

  • 时间复杂度：268. 缺失数字(Missing Number) - 图13。这里假设异或运算的时间复杂度是常数的，总共会进行268. 缺失数字(Missing Number) - 图14次异或运算，因此总的时间复杂度为268. 缺失数字(Missing Number) - 图15。

  • 空间复杂度：268. 缺失数字(Missing Number) - 图16。算法中只用到了268. 缺失数字(Missing Number) - 图17的额外空间，用来存储答案。