别再问我如何写简历了！

只出现一次的(两个)数字③

题目描述：

• 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路：

上面的问题处理和理解起来可能比较容易，但是这个问题可能稍微复杂一点，但是这题可以通过特殊的手段转化为上面只出现一次的一个数字问题来解决，当然核心的位运算也是异或^。

具体思路就是想办法将数组逻辑上一分为二!先异或一遍到最后得到一个数，得到的肯定是a^b(假设两个数值分别为a和b)的值。在看异或^的属性：不同为1，相同为0. 也就是说最终这个结果的二进制为1的位置上a和b是不相同的。而我们可以找到这个第一个不同的位，然后将数组中的数分成两份，该位为0的进行异或求解得到其中一个结果a，该位为1的进行异或求解得到另一个结果b。

具体可以参考下图流程：
 

只出现一次的(一个)数字②

问题描述：

• 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
• 说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗?

分析：

这题和上一题的思路略有不同，这题其他数字出现了3次，那么我们如果直接使用位运算异或操作的话无法直接找到结果，就需要巧妙的运用二进制的其他特性：判断整除求余操作。即判断所有数字二进制1的总个数和0的总个数一定有一个不是三的整数倍，如果0不是三的整数倍那么就说明结果的该位二进制数字为0，同理否则为1.
 

只出现一次的(一个)数字①

问题描述：

• 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
• 说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗?

分析：

这是一道简单的面试题，面试官常问怎么样用不太复杂的方法找出数组中仅出现一次的数字(其他均出现两次)，暴力枚举或者使用其他的存储结构都不够优化，而这个问题最高效的答案就是使用位运算。首先你要注意两点：

• 0和任意数字进行异或操作结果为数字本身.
• 两个相同的数字进行异或的结果为0.

具体的操作就是用0开始和数组中每个数进行异或，得到的值和下个数进行异或，最终获得的值就是出现一次(奇数次)的值。

（编辑：广元站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!