以数学方式检查列表中的唯一项
我一直在解决一些 LeetCode 问题，并遇到了一个有趣的问题。我贴在下面供大家参考：
给定一个数组，其中每个元素出现 3 次，只有一个元素只出现一次。找出出现一次的元素。预期的时间复杂度为 O(n) 和 O(1) 额外空间。
输入：arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3, 3}
输出：2
在给定的数组中，除了 2 出现一次之外，所有元素都出现了 3 次。
我的解决方案是使用哈希图来尝试解决这个问题。不过，我遇到了一个数学解决方案，并想知道为什么会这样：
def singleNumber(nums):
# applying the formula.
return (3 * sum(set(nums)) - sum(nums)) / 2
如果有人能帮助我理解为什么会这样，那就太好了:)
回答
您找到的解决方案实际上并不是您有时会针对这些问题看到的那种“数学”解决方案。 set(nums)创建这些数字的集合，其中每个不同的数字只出现一次——类似于您对哈希图所做的事情。
您知道 sum(nums) = 3*(所有数字的总和) - 2*(唯一数字)。因此，如果您从 计算 3*（所有数字的总和）set，那么您只需减去sum(nums)并除以 2 即可找到唯一的一个。
还有就是不需要你建立一个集合，虽然数学的解决方案：
def findUnique(arr):
c1=0
c2=0
for v in arr:
carry = c1&v
c1 ^= v
c2 ^= carry
threes = c1&c2
c1 &= ~threes
c2 &= ~threes
return c1
你可以在这里试试：https :
//ideone.com/BPoJY5
在此解决方案中，c1和的位c2用作并行计数器来计算值中每个位的出现次数。计算是模 3 完成的，所以最后只剩下出现次数不能被 3 整除的位。