程序典型面试题---数组中只出现一次的数字
浏览数：26 /
时间：2015年06月08日
题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
解法：位异或运算
思路：将问题简化为除了一个数字外，其他数字都出现两次。将数组的结果异或起来，因为出现两次的数组异或结果为0,所以结果异或的结果即为出现一次的数据。
题设的问题将数组分为两组，每组异或的结果即为要求的只出现一次的一个数字。问题的关键是怎么分组刚好能使得两个只出现一次的两个数字位于不同的组，那些出现两次的数字的两次都在相同的组中。
解法：设两个只出现一次的数字为a,b，将数组异或的结果为x=a^b,因为a不等于b,所以x不等于0，即x的二进制中至少有一个1，f(x)=n,n表示x中从最低位开始，第一个为1的位置。按照第n位是否为1，可以
将数组分为两类。这样分类会使得出现两个只出现一次的数位于不同组，且现两次的数字的两次都在相同的组中。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
