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

By Long Luo

Leetcode 268. 丢失的数字 的题解，English version is 4 Approaches: Sorting, Hash, XOR, Math 。

方法一：暴力 + 排序

思路与算法

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

可以使用一个 $\texttt{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. 😉😃💗