L*******o
发帖数: 895 | 1 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这
两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
分析：这是一道很新颖的关于位运算的面试题。
首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都
出现了两次。请写程序找出这个只出现一次的数字。
我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们
从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字
，因为那些出现两次的数字全部在异或中抵消掉了。
我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个
只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办
法就是分别求出这两个只出现一次的数字了。
从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数
字的异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。由于这两个数字
肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中
至少就有一位为1。我们在结果数字中找到第一个 |
g****7
发帖数: 1104 | 2 不明白为啥时间复杂度是O(n)
【在 L*******o 的大作中提到】
: 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这
: 两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
: 分析：这是一道很新颖的关于位运算的面试题。
: 首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都
: 出现了两次。请写程序找出这个只出现一次的数字。
: 我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们
: 从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字
: ，因为那些出现两次的数字全部在异或中抵消掉了。
: 我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个
: 只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办
|
h****h
发帖数: 75 | 3 Smart.
【在 L*******o 的大作中提到】
: 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这
: 两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
: 分析：这是一道很新颖的关于位运算的面试题。
: 首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都
: 出现了两次。请写程序找出这个只出现一次的数字。
: 我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们
: 从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字
: ，因为那些出现两次的数字全部在异或中抵消掉了。
: 我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个
: 只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办
|
z***e
发帖数: 5393 | 4 2n = O(n)
【在 g****7 的大作中提到】
: 不明白为啥时间复杂度是O(n)
|
c**********e
发帖数: 2007 | 5
Ask a weak question: how to do: 我们从头到尾依次异或数组中的每一个数字?
【在 L*******o 的大作中提到】
: 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这
: 两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
: 分析：这是一道很新颖的关于位运算的面试题。
: 首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都
: 出现了两次。请写程序找出这个只出现一次的数字。
: 我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们
: 从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字
: ，因为那些出现两次的数字全部在异或中抵消掉了。
: 我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个
: 只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办
|
Y*****y
发帖数: 361 | 6 整体的idea很巧妙，但是实现的最后一步没完全明白。
假设那两个出现过一次的数是N1, N2。如果那些出现过两次的数在 indexOf1 这一位上
是1（或者0）， 并且在array中出现在N1和N2之后，那num1和num2指的就不是N1和N2的
位置了吧。 |
j****w
发帖数: 6 | 7 同问。
【在 c**********e 的大作中提到】
:
: Ask a weak question: how to do: 我们从头到尾依次异或数组中的每一个数字?
|
c*****y
发帖数: 90 | 8 下面Code就是做这件事情的。
int resultExclusiveOR = 0;
for (int i = 0; i < length; i ++)
resultExclusiveOR ^= inputArray[i];
【在 c**********e 的大作中提到】
:
: Ask a weak question: how to do: 我们从头到尾依次异或数组中的每一个数字?
|
c*****y
发帖数: 90 | 9 LZ的方法很棒。对你的问题有些迷惑。以例子说明吧。
假设那两个出现过一次的数是N1, N2。那些出现过两次的数在indexOf1这一位上是1，
N1在indexOf1这一位上是1，则N2在indexOf1这一位上是0（与N1相反）。即使那些
出现过两次的数在array中出现在N1和N2之后，那么划分的时候它们全部会和N1划分在一起
（因为在indexOf1这一位上均是1）。这样，N1和N2被划分到不同的组，这样题目就被简化
为从各个组中找单个出现单次数的整数。
【在 Y*****y 的大作中提到】
: 整体的idea很巧妙，但是实现的最后一步没完全明白。
: 假设那两个出现过一次的数是N1, N2。如果那些出现过两次的数在 indexOf1 这一位上
: 是1（或者0）， 并且在array中出现在N1和N2之后，那num1和num2指的就不是N1和N2的
: 位置了吧。
|
Y*****y
发帖数: 361 | 10 恩，这个分组idea我明白，不太明白的是code里面最后的实现。那里是用j作为index从
头扫到尾，然后对每个inputArray[j]进行判断，如果indexOf1这一位是1，update
temp1到inputArray[j]，否则update temp2到inputArray[j]。最后的输出结果temp1和
temp2。
作为一个例子，假设N1,N2是出现过一次的数，且N1在那位上是1，N2是0。假设N3,N4出
现过两次，N3该位是1，N4是0。如果这个inputArray是这样的，{N3,N4,N1,N2,N3,N4},
用上面code里面的方法，最后temp1指向第二个N3,temp2指向第二个N4，得出的结果好
像不太对。 就算不用code里面的方法，我的疑问是，对这个例子，如何可以不重新排
序或空间复杂度是O(1)，而直接把原来的数组分成两个组，且具有你说的那个性质（N1
和N2被划分到不同的组，每个组里面其他元素都出现两次）。
或者我的理解有问题，多谢指教。
在一起
被简化
【在 c*****y 的大作中提到】
: LZ的方法很棒。对你的问题有些迷惑。以例子说明吧。
: 假设那两个出现过一次的数是N1, N2。那些出现过两次的数在indexOf1这一位上是1，
: N1在indexOf1这一位上是1，则N2在indexOf1这一位上是0（与N1相反）。即使那些
: 出现过两次的数在array中出现在N1和N2之后，那么划分的时候它们全部会和N1划分在一起
: （因为在indexOf1这一位上均是1）。这样，N1和N2被划分到不同的组，这样题目就被简化
: 为从各个组中找单个出现单次数的整数。
|
m****n
发帖数: 145 | |
c*****y
发帖数: 90 | 12 实际上分组是虚的，并没有重新排序呀。真正的操作是当indexOf1这一位是1的时候与
temp1进行XOR,而当indexOf1这一位是0，与temp2进行XOR。以你的例
子:temp1=N1^N3^N3=N1,temp2=N2^N4^N4=N2。这样结果就出来了。
},
N1
【在 Y*****y 的大作中提到】
: 恩，这个分组idea我明白，不太明白的是code里面最后的实现。那里是用j作为index从
: 头扫到尾，然后对每个inputArray[j]进行判断，如果indexOf1这一位是1，update
: temp1到inputArray[j]，否则update temp2到inputArray[j]。最后的输出结果temp1和
: temp2。
: 作为一个例子，假设N1,N2是出现过一次的数，且N1在那位上是1，N2是0。假设N3,N4出
: 现过两次，N3该位是1，N4是0。如果这个inputArray是这样的，{N3,N4,N1,N2,N3,N4},
: 用上面code里面的方法，最后temp1指向第二个N3,temp2指向第二个N4，得出的结果好
: 像不太对。 就算不用code里面的方法，我的疑问是，对这个例子，如何可以不重新排
: 序或空间复杂度是O(1)，而直接把原来的数组分成两个组，且具有你说的那个性质（N1
: 和N2被划分到不同的组，每个组里面其他元素都出现两次）。
|
Y*****y
发帖数: 361 | 13 哦，明白了，没有看见是XOR，看成赋值了……多谢一系列的耐心解答。
【在 c*****y 的大作中提到】
: 实际上分组是虚的，并没有重新排序呀。真正的操作是当indexOf1这一位是1的时候与
: temp1进行XOR,而当indexOf1这一位是0，与temp2进行XOR。以你的例
: 子:temp1=N1^N3^N3=N1,temp2=N2^N4^N4=N2。这样结果就出来了。
:
: },
: N1
|
b******g
发帖数: 1721 | 14 very good thinking process, admire.... |
