🔍【大厂口试真题】系列开yun体育网，带你攻克大厂口试真题，秒变offer收割机！

❓当天问题：找到⽆序数组中出现两次的两个数

❤️一谈望望文心快码Baidu Comate给出的谜底吧！要是这个问题你也会，也不错在评述区写出你的谜底哦～

@comate在这个问题中，咱们需要在一个无序数组中找到两个只出现一次的数字，而其他数字皆出现两次。要收尾期间复杂度为 O(n) 和空间复杂度为 O(1)，咱们不错使用位运算的妙技，但此次情况稍复杂，因为有两个数出现一次。领先，咱们需要潜入，要是唯唯一个数字出现一次，其尾数字出现两次，咱们不错大致地使用异或运算来找到这个数字。但当今有两个这么的数字，是以咱们弗成奏凯行使相似的范例。不外，咱们不错稍稍修改这个范例来合乎面前的问题。料理决议分为几个法子：整体异或：领先，咱们遍历总计这个词数组，对总计元素进行异或操作。由于除了两个数字外，其他数字皆出现了两次，是以最终的效果将是那两个只出现一次的数字的异或效果。找到任一出现一次的数字的某一位为1的位：这一步是为了将这两个数字隔离开。咱们不错通过查找异或效果中狂放一个为1的位来收尾。这是因为这两个只出现一次的数字在该位上势必是一个为0开yun体育网，另一个为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)，因为咱们只使用了有限的特地变量。