找到⽆序数组中出现两次的两个数
🔍【大厂口试真题】系列，带你攻克大厂口试真题，秒变offer收割机！
❓本日问题：找到⽆序数组中出现两次的两个数
❤️一皆望望文心快码Baidu Comate给出的谜底吧！要是这个问题你也会，也不错在驳倒区写出你的谜底哦～
@comate在这个问题中，咱们需要在一个无序数组中找到两个只出现一次的数字，而其他数字都出现两次。要完竣时间复杂度为 O(n) 和空间复杂度为 O(1)，咱们不错使用位运算的妙技，但此次情况稍复杂，因为有两个数出现一次。率先，咱们需要分解，要是只须一个数字出现一次，其尾数字出现两次，咱们不错浅易地使用异或运算来找到这个数字。但目下有两个这么的数字，是以咱们不行径直利用通常的顺次。不外，咱们不错略略修改这个顺次来符合刻下的问题。经管决策分为几个才调：整体异或：率先，咱们遍历通盘数组，对所有元素进行异或操作。由于除了两个数字外，其他数字都出现了两次，是以最终的后果将是那两个只出现一次的数字的异或后果。找到任一出现一次的数字的某一位为1的位：这一步是为了将这两个数字分离开。咱们不错通过查找异或后果中肆意一个为1的位来完竣。这是因为这两个只出现一次的数字在该位上势必是一个为0，另一个为1。笔据这一位将原数组分红两组：目下，咱们再次遍历数组，笔据上一步找到的位将数组中的数字分红两组。一组包含所有在该位上为1的数字，另一组包含所有在该位上为0的数字。由于咱们笔据的是两个只出现一次的数字在该位上的不同进行分组，因此这两个数字会被分到不同的组中，而其他成对出现的数字会被分到归并个组中。对每组分别进行异或操作：终末，咱们对每组分别进行异或操作。由于每组中除了一个数字外，其他数字都是成对出现的，是以异或的后果等于阿谁只出现一次的数字。底下是这个算法的伪代码完竣：# Step 1: 整体异或xorResult = 0for num in nums: xorResult ^= num# Step 2: 找到任一出现一次的数字的某一位为1的位bit = 1while (xorResult & bit) == 0: bit <<= 1# Step 3 & 4: 笔据这一位将原数组分红两组并分别异或a, b = 0, 0for num in nums: if num & bit: a ^= num else: b ^= num# a 和 b 等于两个只出现一次的数字return a, b这个算法的时间复杂度是 O(n)，因为咱们只遍历了数组两次。空间复杂度是 O(1)，因为咱们只使用了有限的荒芜变量。
