Google电面 08/25/2015

坐看云起 发表于 2015-9-22 11:05
这个过程是O(k)的，此处k==3，因为数组长度取决于要找的目标所占比例，所以这道题可以当作是常量时间

不太知​​道要怎么检查能用这个example 说说吗?

5 3 5 3 1 2

最后会有5(count =1) 3(count=1) 1(count=0) 怎么知道哪个是最后的结果?

这三个candidate只能在遍历一次原来数组来确定了，这里只能说它们三个有可能是，但不能保证是。。。。

say543 发表于 2015-9-23 11:25
不太知道要怎么检查能用这个example 说说吗?

5 3 5 3 1 2

我觉得是这样的，5 3 5 3 1 2，5和3都满足大于四分之一的这个条件，也就是说，如果popular number只有一个(频率最高的一个)，那么这个输入是invalid。如果这个输入是valid,那么就有两个popular number

夜行码农耗子 发表于 2015-9-28 11:01
我觉得是这样的，5 3 5 3 1 2，5和3都满足大于四分之一的这个条件，也就是说，如果popular number只有一 ...

不太懂 所谓的valid or invalid 能说说吗?

say543 发表于 2015-9-29 13:11
不太懂 所谓的valid or invalid 能说说吗?

就是说，如果输入只有一个大于四分之一的数，那么这个算法能输出那个数，如果输入有多个满足条件的数，那么就全都输出呗

say543 发表于 2015-9-29 13:11
不太懂 所谓的valid or invalid 能说说吗?

就是后加入的数可能只有很少，但是因为数组已经数完了，所以不会去掉它。需要再数一遍看它的数量是不是大于1/4数组长度。