[Leetcode][268. 丢失的数字] 4种方法：排序，哈希表，异或，数学公式

By Long Luo

Leetcode 268. 丢失的数字 ，题目如下：

268. 丢失的数字

给定一个包含[0, n]中n个数的数组nums，找出[0, n]这个范围内没有出现在数组中的那个数。

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

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

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

示例 4：
输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围[0,1]内。1是丢失的数字，因为它没有出现在 nums 中。
 
提示：
n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
nums 中的所有数字都 独一无二
 
进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

方法一：暴力 + 排序

思路与算法

这是一道简单题。首先想到的方法是先进行排序，然后遍历数组，找到值不同的那个数字，如果都相同，那么结果就是$len$。

代码如下所示：

public int missingNumber(int[] nums) {
	int len = nums.length;
	Arrays.sort(nums);
	for (int i = 0; i < len; i++) {
		if (i != nums[i]) {
			return i;
		}
	}

	return len;
}

复杂度分析：

• 时间复杂度：$O(n \log n)$，其中$n$是数组$\textit{nums}$的长度。排序的时间复杂度是$O(n \log n)$，遍历数组寻找丢失的数字的时间复杂度是$O(n)$，因此总时间复杂度是$O(n \log n)$。
• 空间复杂度：$O(\log n)$，其中$n$是数组$\textit{nums}$的长度。空间复杂度主要取决于排序的递归调用栈空间。

方法二：HashSet

可以使用一个HashSet来记录数组中出现的数，将时间复杂度降低为$O(n)$。

首先遍历数组$\textit{nums}$，记录数组中的每个元素，然后检查从$0$到$n$的每个整数是否在哈希集合中，不在哈希集合中的数字即为丢失的数字。由于哈希集合的每次添加元素和查找元素的时间复杂度都是$O(1)$，因此总时间复杂度是$O(n)$。

public static int missingNumber_set(int[] nums) {
	int len = nums.length;
	Set<Integer> set = new HashSet<>();
	for (int i = 0; i < len; i++) {
		set.add(nums[i]);
	}

	for (int i = 0; i <= len; i++) {
		if (set.add(i)) {
			return i;
		}
	}

	return len;
}

复杂度分析：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

方法三：异或(XOR)

数组$\textit{nums}$中有$n$个数，在这$n$个数的后面添加从$0$到$n$的每个整数，则添加了$n + 1$个整数，共有$2n + 1$个整数。

在$2n + 1$个整数中，丢失的数字只在后面$n + 1$个整数中出现一次，其余的数字在前面$n$个整数中（即数组中）和后面$n + 1$个整数中各出现一次，即其余的数字都出现了两次。

根据出现的次数的奇偶性，可以使用按位异或运算得到丢失的数字。按位异或运算$\oplus$满足交换律和结合律，且对任意整数$x$都满足$x \oplus x = 0$和$x \oplus 0 = x$。

由于上述$2n + 1$个整数中，丢失的数字出现了一次，其余的数字都出现了两次，因此对上述$2n + 1$个整数进行按位异或运算，结果即为丢失的数字。

public static int missingNumber_xor(int[] nums) {
    int xor = 0;
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        xor ^= nums[i];
    }

    for (int i = 0; i <= len; i++) {
        xor ^= i;
    }

    return xor;
}

复杂度分析：

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

方法四：数学公式

思路与算法

从$0$到$n$的全部整数之和记为$\textit{total}$，根据等差数列求和公式，有：

$\textit{total} = \sum_{i=1}^n = \dfrac{n(n+1)}{2}$

将数组$\textit{nums}$的元素之和记为$\textit{arrSum}$，则$\textit{arrSum}$比$\textit{total}$少了丢失的一个数字，因此丢失的数字即为$\textit{total}$与$\textit{arrSum}$之差。

代码如下所示：

public static int missingNumber_sum(int[] nums) {
    int len = nums.length;
    int sum = len * (len + 1) / 2;
    int arraySum = 0;
    for (int x : nums) {
        arraySum += x;
    }

    return sum - arraySum;
}

复杂度分析：

• 时间复杂度：$O(n)$，其中$n$是数组$\textit{nums}$的长度。需要$O(1)$的时间计算从$0$到$n$的全部整数之和以及需要$O(n)$的时间计算数组$\textit{nums}$的元素之和。
• 空间复杂度：$O(1)$。

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗