老二其实很悲催 - 未名空间MITBBS历史存档

z*y2018-07-05 07:07

1 楼

Given an array of numbers and a number X
find two elements a, b from the array such that a+b = X
My solution is sorting first then binary search
O(n log n)
I don't think it can be improved further, right?

h*p2018-07-05 07:07

2 楼

就像我们不能用自己的眼睛看到自己的脸一样，我们有时候不能确定人类自身的社会行
为特征到底是什么样子，它的由来演变是如何发生的。于是聪明的人就会建议去找像镜
子那样的参照物，用以做比较分析。历史就是一面镜子，人类近亲的动物社会也是一面
镜子，拿过来照照，有时真能触发一些特别的感悟。
在适者生存的前提下，自然的演变是遵循最简单最高效原则，这也是奥克汉姆剃刀法则
想要表达的意思。人和那些灵长类动物社会的本质其实都是相通的，一个共同的基本特
点就是，有的成员想建立和维持一种规则秩序，而另有成员想要打破这种规则和秩序。
无一例外，这些规则和秩序都是围绕着生存和繁衍。简单说起来，在动物社会里，寻偶
配对繁育子嗣也是要简单高效，不能浪费能量，而雄性动物和雌性动物的生育能力和周
期是有差别的，两不耽误理论上可行，实际操作起来也不那么容易。比如，我们可以说
男人的生育能力是无限的，因为他在性成熟后，就无时无刻不在产生精子，这个能力可
能一直能存在到他的生命终结。而女人的生育能力是有限的，她能生成的卵子的数量和
排放的时间是有限的。对于雄性来说，怎么能够利用雌性的短暂生育时间窗口，把自己
的基因尽量多地延续下去，就是他生活的第一要务。而对于雌性来说，青春短暂，怎么
能及时得到最优良的异性播种，怎么能在自己的生育哺乳期确保母子的安全资源的供给
，这些则是她的首选考量。综合起来看，好像是雄性更侧重于对量的追求，而雌性更在
乎对质的考量，总而言之，这些生存和繁衍的需求合成了社会演变的原始推动力。
非常有意思的现象，同为人类近亲的大猩猩和黑猩猩，他们的基础社会形态却截然不同
，大猩猩是典型的以猴王统治的首领部落，而黑猩猩则是有点众生平等味道的母系群落
。按照有些动物行为学家的说法，造成这种生存结构不同的深层原因，竟是雌性的发情
期规律。以他们所根据的研究表明，一个群落里雌性大猩猩的排卵期或发情期是大致相
同的，所以，雄性的猩猩们早早地就开始为争夺交配权而展开了争斗。这对雌性们来说
也是乐见其成，这样一来，到时候她们就不必为了选择最优良种而花费精力了，而且顺
从了竞争出来的猴王，怀孕以后衣食无忧，对自己基因的传续也是个利好。对于雄性中
的强者来说，这也是个一劳永逸的事情，打败了竞争者后，他所要做的就是在雌性发情
的那个窗口，集中精力和体力，一次性依次满足群里母猩猩们的要求就是了。
而黑猩猩种群中的雌性和人类的特点有些相像，她们的发情排卵期不一致，这样一来，
没有男的有能力长时间全天候地罩住此起彼伏地母性需求，所以在黑猩猩社会中，男子
们就是随时随地逮住机会就上了。从大猩猩黑猩猩这两个物种性行为的特点来看，就不
难理解他们之间体征的不同了。对于雄性大猩猩来说，要紧的是打败别的对手，这就要
求他的胳膊要粗壮，牙齿要尖锐。而对于雄性黑猩猩来说，体型肌肉的块头大小就不是
十分的要紧，关键是要有连续交配连续供应精子的能力。所以，在灵长类动物中，黑猩
猩的睾丸是最为巨大的。
虽然称霸的大猩猩貌似独享了与群落中异性的交配权，但动物学家们通过DNA的追踪测
试发现，他的妻妾们肚子里所怀有的，也未必就全都是猴王的骨血。这里有相当的比例
是别的猩猩的后代。但这些孩子基本不会说是来自那些排行老二或是中档附近的雄性，
而是那些从来入不了大王法眼的最低档的雄性loser们的后裔子孙。这样说起来，在大
猩猩那样需要为生存拼命竞争的世界，要想留下自己的基因，为自己的精子找上一条出
路，你要么就去当王者，要么就要装孙子。

l*82018-07-05 07:07

3 楼

can be O(n) time.

g*e2018-07-05 07:07

4 楼

if you have more memory, you can use a hashtable to store all the values and
check each's complimentary value in O(n)

p*22018-07-05 07:07

5 楼

这不是经典题吗？sort之后two pointer,比binary search 复杂度低。