LeetCode 面试题56 - I. 数组中数字出现的次数 | Python（leetcode会员）

LeetCode 面试题56 - I. 数组中数字出现的次数 | Python（leetcode会员）

面试题56 - I. 数组中数字出现的次数

题目

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]

输出：[1,6] 或 [6,1]

示例 2：

输入：nums = [1,2,10,4,1,4,3,3]

输出：[2,10] 或 [10,2]

限制：

2 <= nums <= 10000

解题思路

思路：异或，位运算

先说下异或的性质：二进制位同一位相同则为 0，不同则为 1。

再说说一下异或的规律：

若两数值相同，两者的异或结果为 0，（即是任何数与自身异或结果为 0）

任何数与 0 异或结果为本身

同时异或是满足交换律，结合律的（数学符合：⊕）

交换律： a ⊕ b = b ⊕ a

结合律： a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c

回来看本题，题目说明，【整型数组 nums 中，除两个数字之外，其他数字都出现了两次】。那么根据交换律、结合律将相同数字进行异或运算，那么相同数字都会变为 0，再根据第二条规律，那么剩下的出现一次的数字。

在这里主要需要实现的如何确保将数组分成两组，使得：

只出现一次的数字，在不同的两组；

相同的数组出现在相同的组。

只有这样，每组进行异或运算的时候，最终才会剩下单独的数字。那么该如何进行分组？特别是如何将两个不同的数字分到不同的组？

具体实现代码如下。

代码实现

class Solution:

def singleNumbers(self, nums: List[int]) -> List[int]:

res = 0

# 全员进行异或

for num in nums:

res ^= num

# 找出不为 0 的最低位

# & 位运算的使用

div = 1

while (div & res == 0):

div <<= 1

# 进行分组

p, q = 0, 0

for num in nums:

if num & div:

p ^= num

else:

q ^= num

return [p, q]

实现结果

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。