一点古老的算法魔法，或者解决 LeetCode 中一系列有趣的任务

前段时间，我在 leetcode.com 网站上发现了一系列有趣的任务。任务本身并不太困难，但它们的解决方案却相当有趣。而且，这类问题经常出现在大公司的面试中，了解他们的解决方法是非常有益的。

第一个任务是 136. 单数（简单）

给定一个非空整数数组，其中每个元素除了一个之外都出现两次，您需要找到没有配对的元素。以 O(n) 时间复杂度和恒定的额外内存解决问题。

示例1：

输入：nums = [1, 3, 3, 2, 6, 2, 1]

输出：6

示例2：

输入：nums = [12, 1, 1, 7, 1, 12, 1]

输出：7

示例3：

输入：nums = [6]

输出：6

我们将利用 XOR 函数属性，仅当其操作数不同时才产生 1。通过遍历数组的所有元素并对它们执行按位异或，我们将所有相同的位值清零。结果，剩下的就是期望的结果。

这是一个简短的 Python3 解决方案代码：

 def single_number(nums: list) -> int: result = 0 for el in nums: result ^= el return result

我们仅使用整数占用的额外内存，并在一次遍历给定数组中找到解决方案，从而获得 O(n) 复杂度。这是一个简洁而优雅的解决方案。

第二题是137.单数II（中等难度）

给定一个非空整数数组，其中除一个之外每个元素都出现三次，并且只有一个元素出现一次，我们需要找到这个唯一元素。以 O(n) 时间复杂度和恒定的额外内存解决问题。

示例1：

输入：nums = [3, 1, 3, 3]

输出：1

示例2：

输入：nums = [12, 1, 1, 5, 1, 12, 12]

输出：5

示例3：

输入：nums = [6]

输出：6

不幸的是，在这种情况下我们不能使用前面的技巧，因为我们不能将所需位置处的配对位转为零。将给定数组转换为上一个任务的格式，然后以类似的方式解决它是很诱人的。

以这种方式推理，很容易注意到，如果我们知道在遍历数组时已经遇到了数字 N 两次（或三次），我们可以将与 N 的额外异或添加到我们获得的总和中。这将使最终的异或与该数字偶数，从而将其从最终总和中删除，剩下的就是我们的答案。

 def single_number_ii(nums: list) -> int: mem = {} result = 0 for el in nums: if not mem.get(el, False): mem[el] = 1 else: mem[el] += 1 if mem[el] == 2: result ^= el result ^= el return result

不幸的是，这个解决方案最多需要 (len(nums)-1)/3 的内存，这不能被视为持续消耗，所以我们必须寻找另一个解决方案。

让我们尝试改变我们的方法。

之前，我们使用了 XOR（表示模 2 加法）。如果我们实现了模 3 的加法，我们就可以轻松应用前面示例中的技巧。

如果我们可以在第一次遇到答案时将一个数字放入累加器中，第二次将其放入累加器中，并在第三次中将答案和累加器都归零，这将帮助我们一次性解决问题额外消耗内存的列表恰好等于两个整数，满足任务要求。

那么，让我们应用更多按位魔法：

 def single_number_137_ii(nums: list) -> int: ans, acc = 0, 0 for n in nums: ans = ans ^ n & ~acc acc = acc ^ n & ~ans return ans

这样，所有三重数字都被清零，我们只剩下只出现一次的数字。

第三个任务是260.单数III（中等难度）

给定一个非空整数数组，其中每个元素都出现两次，除了两个仅出现一次的元素之外，我们需要找到这些唯一元素。目标是以 O(n) 时间复杂度和恒定的额外内存解决问题，并且唯一元素的顺序并不重要。

示例1：

输入：nums = [1, 2, 1, 3, 2, 5]

输出：[3, 5]

示例2：

输入：nums = [1, -2]

输出：[-2, 1]

显然，我们可以使用 XOR 运算轻松消除所有配对数字，就像我们在解决第一个任务时所做的那样。任务的复杂性在于识别任何唯一的数字，然后可以通过将其与我们的异或和进行异或运算来轻松计算第二个数字。

为了实现这一点，我们只需要找到这些唯一数字之间的任何不同位。然后，我们再次迭代数组，执行异或求和，并将结果分为两组 - 对于设置了该位的数字和对于它为 0 的数字。结果，我们获得了所需的唯一元素。

 def single_number_260(nums: list) -> int: res1, res2 = 0, 0 glob_xor = 0 for n in nums: glob_xor ^= n diff_bit = glob_xor & ~(glob_xor - 1) for n in nums: if n & diff_bit: res1 ^= n else: res2 ^= n return [res1, res2]

尽管必须迭代数组两次，但复杂度仍然是 O(n)，并且内存消耗仅为 2 个整数。

注意：尽管 Python 中的 int 与其他语言中的 int 并不完全相同，但我们将其大小视为常量