【13回顾】爸爸去哪灵水村观后 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>TVChinese - 中文电视

【13回顾】爸爸去哪灵水村观后

【13回顾】爸爸去哪灵水村观后# TVChinese - 中文电视

L*o2014-01-14 08:01

1 楼

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这
两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
分析：这是一道很新颖的关于位运算的面试题。
首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都
出现了两次。请写程序找出这个只出现一次的数字。
我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们
从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字
，因为那些出现两次的数字全部在异或中抵消掉了。
我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个
只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办
法就是分别求出这两个只出现一次的数字了。
从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数
字的异或结果。因为其他数字都出现了两次，在异或中全部抵消掉了。由于这两个数字
肯定不一样，那么这个异或结果肯定不为0，也就是说在这个结果数字的二进制表示中
至少就有一位为1。我们在结果数字中找到第一个

c*n2014-01-14 08:01

2 楼

从来没看见什么卡或者program给amazon cashback。哪怕0.1％都没有

a*i2014-01-14 08:01

3 楼

俺有亲戚在小县城里，有年亲戚给我打电话，说阿飞呀，我听说你有办法查高考的分。
我说对呀，你有什么关系要查查。对面说太好了太好了，我还真有关系。
先交代一下背景。这个查分其实就是在正式公布高考成绩之前，我就能查到你考了多少
，在全省是多少名。这后一个数据基本可以推测出你上没上线，上了哪条线。听起来牛
皮，说穿了一文不值，因为高考统分在我家单位，数据中心的人我从小混得溜熟，打个
电话报个号，对面也就是一句select from的事情对不？
然后我亲戚就报了个号，俺查了查说叫这同学明年再考吧。我亲戚说你没查错吧？人自
己估的是重点大学的线。我说这哥们儿估分的水平稍微弱点，把丫分数乘个５，大概就
重点了。
这事儿我以为就完了，结果第二天亲戚忽然给我打电话叫我出来，说他们现在就在单位
门外。
我喝个水先

m*y2014-01-14 08:01

4 楼

自己的旧文，爸爸去哪被评为我的2013最爱。
看了两期，最大的感受是好想有个自己的娃呀，孩子们真的都很可爱呢。
1，Cindy 开场大哭三个多小时，和天天上交玩具之后闹情绪。可能是之前没有跟孩子
讲清楚吧。孩子遇到突发情况害怕，不高兴。五岁了，应该能懂道理了，提前告诉孩子
，我们这次去哪里，多久，可能遇到些困难，但是我们一起克服就能坚持下来。这是一
次冒险，如果能克服困难就是很棒的小朋友。比如，去看医生打针，提前告诉小朋友，
会有一点疼，但是如果能坚持下来，就是坚强勇敢的好孩子。如果骗孩子说一点都不疼
的，或者让他毫无准备的去面对针头，孩子会很害怕。可能孩子对未知的恐惧比真正的
疼痛会更可怕吧。同样，去录像也是，告诉孩子就三天结束，可能会遇到困难，但是要
坚持忍耐，才能赢得最后胜利！出了状况就鼓励孩子，之前我们都下决心要克服困难了
，所以现在的考验不算什么的，对吧？
2，教孩子唱歌。所有的孩子都没学会那首歌，因为，我觉得对小孩子来说歌词实在太
长了。田亮很有爱的跟女儿说，学不会就算了吧，玩儿去吧。真的很让我动容呢。但是
既然参加了活动，还是配合一下比较好。可以鼓励孩子说，唱不好没关系，实在不会唱
呢，就在别的小朋友唱的时候，你来拍手。这样也是参与了这个唱歌的活动，大家都很
开心，这个很重要。或者降低一下要求，比如说，爸爸唱每一句的前面的字（因为歌词
实在太长了），你顺着唱最后三个字。这样有爸爸提醒和带领，也算完成了唱歌，这就
非常好了。Kimi虽然没有唱歌，但是大人唱歌的时候他跳舞，很认真的参与，我认为是
没学会唱歌的孩子里面表现最好的了。小娃们对正儿八经唱歌很抵触，就像张亮，我们
一边玩，一边学好啦。特别是一天很多零散时间，到后来大家都把学唱歌的事情忘记了
。如果爸爸能一直记住，在旁边哼唱，可能孩子能多学一点吧。
3，比赛的输赢，孩子们都想赢的，对自己没有准备好的比赛，比如唱歌，会害怕和逃
避。应该告诉孩子，没有学会，或者唱的不好也没关系的。比如石头说，没有学过唱这
个歌，不应该当面说他胡说八道，应该说，我们今天没学会，可能唱歌赢不了，但是我
们今天找锅表现的非常好，放羊也表现的非常好。唱歌这个方面我们下次努力，这次没
学会真的没什么大不了的。别的小朋友唱的好，我们虽然不会唱，但是可以好好听，一
边拍手，然后夸奖她唱的好。还有就是做饭的输赢，天天要自己去找狗尾巴草给爸爸，
真的很感动。应该抱抱孩子，说比赛虽然输了，但是你认为爸爸做的最好，这个才是爸
爸认为最重要的。虽然输了，但是爸爸努力过了，就很好了。别的小朋友可能觉得其他
人做的好吃，应该尊重他们的看法。天天帮爸爸拉票很可爱，就是用威胁不给洗澡的方
法容易让小朋友不远妥协。应该注意拉帮结伙的方法，比如，刚才我投票给你爸爸啦，
你也投票给我爸爸好不好？
4，批评教育孩子。虽然我真的很想一下子把所有的好品格都灌输给孩子，勇敢，坚强
，善良，友好，热情，礼貌。同时也想交很多技能，比如唱歌，跳舞，说儿歌。但是还
应该每天最多教一样，每天也就只批评一次。毕竟还是孩子，时间还很多，每天只教一
个技能，只批评一次，让孩子有更多的时间去玩，感受爸爸的爱护。吓唬孩子虽然很有
效，但是还是不要了吧。比如爸爸吓唬语龄说，不学唱歌不让吃中午饭了，孩子一把拿
过曲谱。虽然很有效啦，最小的小妹是唯一表演唱歌的。但是，让孩子坚信父母无条件
的爱和安全感，比学会一首歌重要。真的想让孩子知道，即使学不会，考试没考好，输
掉比赛，也不会没有饭吃，生活还是会继续。石头虽然最大，但是毕竟摔坏了右手，生
活不方便，需要爸爸喂饭。情绪可能会不稳定。就像郭涛说的，能来参加已经就是非常
棒了。在孩子生活不便的时候，有点哼哼唧唧，应该多赞扬，说能来已经很好了，石头
非常坚强，而且一天表现也很好，如果现在能快乐的吃饭，就更好了！孩子应该不至于
在吃晚饭和唱歌的时候闹情绪吧。把孩子一个人推到门外面，或者说儿子咩咩咩不男人
，我觉得对孩子有点过了。

g*72014-01-14 08:01

5 楼

不明白为啥时间复杂度是O(n)

【在 L*******o 的大作中提到】

: 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这
: 两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
: 分析：这是一道很新颖的关于位运算的面试题。
: 首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都
: 出现了两次。请写程序找出这个只出现一次的数字。
: 我们想到了异或运算的性质：任何一个数字异或它自己都等于0。也就是说，如果我们
: 从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字
: ，因为那些出现两次的数字全部在异或中抵消掉了。
: 我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个
: 只出现一次的数字，而其他数字都出现两次。如果能够这样拆分原数组，按照前面的办

f*d2014-01-14 08:01

6 楼

Amazon Chase cc

【在 c******n 的大作中提到】

: 从来没看见什么卡或者program给amazon cashback。哪怕0.1％都没有

M*u2014-01-14 08:01

7 楼

唉，熊孩子从来不按常理出牌，看你写的挺高兴，有孩子气死你。

【在 m**********y 的大作中提到】

: 自己的旧文，爸爸去哪被评为我的2013最爱。
: 看了两期，最大的感受是好想有个自己的娃呀，孩子们真的都很可爱呢。
: 1，Cindy 开场大哭三个多小时，和天天上交玩具之后闹情绪。可能是之前没有跟孩子
: 讲清楚吧。孩子遇到突发情况害怕，不高兴。五岁了，应该能懂道理了，提前告诉孩子
: ，我们这次去哪里，多久，可能遇到些困难，但是我们一起克服就能坚持下来。这是一
: 次冒险，如果能克服困难就是很棒的小朋友。比如，去看医生打针，提前告诉小朋友，
: 会有一点疼，但是如果能坚持下来，就是坚强勇敢的好孩子。如果骗孩子说一点都不疼
: 的，或者让他毫无准备的去面对针头，孩子会很害怕。可能孩子对未知的恐惧比真正的
: 疼痛会更可怕吧。同样，去录像也是，告诉孩子就三天结束，可能会遇到困难，但是要
: 坚持忍耐，才能赢得最后胜利！出了状况就鼓励孩子，之前我们都下决心要克服困难了

h*h2014-01-14 08:01

8 楼

Smart.

【在 L*******o 的大作中提到】

y*i2014-01-14 08:01

9 楼

it is amazon's policy
amazon does have an affiliate program, but its terms don't allow cash back

【在 c******n 的大作中提到】

: 从来没看见什么卡或者program给amazon cashback。哪怕0.1％都没有

z*e2014-01-14 08:01

10 楼

2n = O(n)

【在 g****7 的大作中提到】

: 不明白为啥时间复杂度是O(n)

r*e2014-01-14 08:01

11 楼

just support charity

【在 c******n 的大作中提到】

: 从来没看见什么卡或者program给amazon cashback。哪怕0.1％都没有

c*e2014-01-14 08:01

12 楼

Ask a weak question: how to do: 我们从头到尾依次异或数组中的每一个数字?

【在 L*******o 的大作中提到】

f*e2014-01-14 08:01

13 楼

citi forward 5% TYP

Y*y2014-01-14 08:01

14 楼

整体的idea很巧妙，但是实现的最后一步没完全明白。
假设那两个出现过一次的数是N1, N2。如果那些出现过两次的数在 indexOf1 这一位上
是1（或者0），并且在array中出现在N1和N2之后，那num1和num2指的就不是N1和N2的
位置了吧。

f*q2014-01-14 08:01

15 楼

amazon大牌，不屑于cb拉客户

j*w2014-01-14 08:01

16 楼

同问。

【在 c**********e 的大作中提到】

:
: Ask a weak question: how to do: 我们从头到尾依次异或数组中的每一个数字?

s*g2014-01-14 08:01

17 楼

forward和amazon卡都有>1%的cashback

【在 c******n 的大作中提到】

: 从来没看见什么卡或者program给amazon cashback。哪怕0.1％都没有

c*y2014-01-14 08:01

18 楼

下面Code就是做这件事情的。
int resultExclusiveOR = 0;
for (int i = 0; i < length; i ++)
resultExclusiveOR ^= inputArray[i];

【在 c**********e 的大作中提到】

:
: Ask a weak question: how to do: 我们从头到尾依次异或数组中的每一个数字?

a*92014-01-14 08:01

19 楼

forward 的要大一点点吧

c*y2014-01-14 08:01

20 楼

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的
: 位置了吧。

c*72014-01-14 08:01

21 楼

用amazon信用卡呀。
amazon这么有名，凭什么让fatwallet这些网站赚钱，不需要做这样的广告

【在 c******n 的大作中提到】

: 从来没看见什么卡或者program给amazon cashback。哪怕0.1％都没有

Y*y2014-01-14 08:01

22 楼

恩，这个分组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*n2014-01-14 08:01

23 楼

smart solution！

c*y2014-01-14 08:01

24 楼

实际上分组是虚的，并没有重新排序呀。真正的操作是当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*y2014-01-14 08:01

25 楼

哦，明白了，没有看见是XOR，看成赋值了……多谢一系列的耐心解答。

【在 c*****y 的大作中提到】

: 实际上分组是虚的，并没有重新排序呀。真正的操作是当indexOf1这一位是1的时候与
: temp1进行XOR,而当indexOf1这一位是0，与temp2进行XOR。以你的例
: 子:temp1=N1^N3^N3=N1,temp2=N2^N4^N4=N2。这样结果就出来了。
:
: },
: N1

b*g2014-01-14 08:01

26 楼

very good thinking process, admire....