Linux论坛 » 算法学习 » 解一道baidu面试题

chuter 发表于 2008-5-12 16:03

解一道baidu面试题

题意如下：
    有一个数在一个数组中出现50%以上，让你在O(n)的时间内，O(1)的空间复杂度，找出那个数，其中数组内的数都是随机数，但是有范围。


当时没想出什么好的方法，就没再想。第二天早上去植树的时候，挖完了四个大坑，休息时看着zn在那儿挖坑，看着一排坑，一个一个插入树苗填上，看着看着想到了这道题的解决思路，大致如下：
一个数超过了50%，那么就每次拿这个数（设为A）和其它数抵消，最后剩下的肯定是它，但是空间复杂度是O(1)，所以只能顺序的读入数组，且不能整个存储。那么就不能保证每次都是拿A和非A抵消，再一想，只要抵消两个不同的数就行了，那么如果碰到两个相同的数呢，留一个，但是要记录重复的次数，稍加考虑就能看出，这个次数始终记录的都会是一个数重复的次数，不会出现要同时记录多个数的重复次数，因为遇到不同的就抵消了，这样的话只要开3个数的空间，顺序扫描一边数组就能得出所要求的数。下面举个简单例子：

    数组内数为：2 2 2 4 4 3 3 2 2 2
    经过三步处理之后当前数是2，重复次数是3，遇到4，当前数还是2，重复数-1=2，如此下去，当遇到第二个3时，当前数是3，遇到下一个2，抵消，再遇到2，当前数就是2，最后当前数仍是2，重复数是1，则所求是2...

cnangel 发表于 2008-5-12 17:37

44433322222222

chuter 发表于 2008-5-12 18:08

回复 2楼 cnangel 的帖子

前面三个4和三个3抵消后只剩2了，最后当前数是2，重复数是8，所求是2

锅盖头 发表于 2008-5-14 07:39

顶呀 呵呵

seeman 发表于 2008-5-14 18:11

:lol

bluebird_shao 发表于 2008-5-29 22:18

学到东西了

赵龙 发表于 2008-7-2 13:24

想法很独特，受教了！

sjktyr 发表于 2008-7-3 20:39

有点像选择题啊........对错的概率都是50%。。。。。

killer 发表于 2008-7-12 15:57

学习了. . ..:lol

yuweilbdf 发表于 2008-8-26 13:26

想法独到，学习了，不错不错;P

leius 发表于 2008-10-3 23:41

回复 1楼 chuter 的帖子

每次去掉两个不一样的数，剩下的就是你要找的。

grjboy30 发表于 2008-12-20 11:55

:o照LZ这么说 感觉排列的  数组类似于  数组内数为：2 2 2 4 4 3 3 2 2 2 都可行喽~

spreadyourwings 发表于 2009-4-3 22:26

真的是很不错的想法

sslicheng 发表于 2009-6-16 18:39

受教了，谢谢！

qiqjiao 发表于 2010-9-9 22:31

试问楼主证明过算法的正确性吗？！
看这个序列：9,1,9,2,9,3,9,4,8,8,8。“9”是次数最多的，但是按楼主的算法结果是“8”！？

我的解法：
不妨假设有N个数，它们都是32Bits的int，设x出现次数超过50%。[color=Red]如果我们把x表示成二进制0bxx...xx（x=0/1)，因为x出现次数超过50%，那么x中的每一位出现次数也会超过50%，反之如果知道了这N个数某一位上出现次数超过50%的位（“0”或“1”），则可推出x这一位置上的位。[/color]这样用一个大小为32的数组，设为BitCount[32]，去统计这N个int的0~31位置上的“1”（“0”也类似）的出现次数。完成后，如果某一位的计数，例如BitCount[3]超过了50%（N/2），则说明这N个数第“3”位置上“1”出现次数超过了50%，反之“0”超过了50%，从而可以推断出x（待求数）第“3”位置上为“1”，反之为“0”。进行32次此类操作便可得出x。
此方法要用32个变量，虽比不上楼主的3个变量，但至少它是[color=Red]正确的[/color]。

查看完整版本: 解一道baidu面试题