By Long Luo

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

方法一：暴力 + 排序

思路与算法

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

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11

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)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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\) 个整数进行按位异或运算，结果即为丢失的数字。

1
2
3
4
5
6
7
8
9
10
11
12
13

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}\) 之差。

代码如下所示：

1
2
3
4
5
6
7
8
9
10

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. 😉😃💗