🔍【大厂口试真题】系列女同，带你攻克大厂口试真题，秒变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)，因为咱们只使用了有限的独特变量。