B*****p
发帖数: 339 | 1 有个数组,其中三个数出现超过数组长度1/4, 怎么线性算法找出这三个数? |
r****o
发帖数: 1950 | 2 好像BlueAnt以前做过这题，呵呵。
【在 B*****p 的大作中提到】
: 有个数组,其中三个数出现超过数组长度1/4, 怎么线性算法找出这三个数?
|
B*****p
发帖数: 339 | 3 有link吗?
【在 r****o 的大作中提到】
: 好像BlueAnt以前做过这题，呵呵。
|
l******c
发帖数: 2555 | 4 three elements, a b c (more often to more less), all other elements are
less often than c, so, excluding a and b, this becomes c is over 50% while
all other elements are less than 50%.
【在 B*****p 的大作中提到】
: 有个数组,其中三个数出现超过数组长度1/4, 怎么线性算法找出这三个数?
|
g*****a
发帖数: 1457 | |
B*****p
发帖数: 339 | 6 how do we know a and b before we handle c?
【在 l******c 的大作中提到】
: three elements, a b c (more often to more less), all other elements are
: less often than c, so, excluding a and b, this becomes c is over 50% while
: all other elements are less than 50%.
|
l******c
发帖数: 2555 | 7 we do not need know a b c which is more often,
we only need three variables and three counters, everytime new element comes
in, search, if found, ++ on the counter, else -- on the smallest(or biggest
????) counter, if the counter equals 0, assign this new element.
You can write the code to test it. and post the results here
【在 B*****p 的大作中提到】
: how do we know a and b before we handle c?
|
I*********g
发帖数: 93 | |
g*******y
发帖数: 1930 | 9 其实就是那个题：
“有一个数出现的次数，>1/2*数组总个数，O(N)时间O(1)空间找出来”
的延伸而已
【在 B*****p 的大作中提到】
: 有个数组,其中三个数出现超过数组长度1/4, 怎么线性算法找出这三个数?
|
s*******a
发帖数: 42 | 10 让我想起了编程之美的发贴水王
【在 B*****p 的大作中提到】
: 有个数组,其中三个数出现超过数组长度1/4, 怎么线性算法找出这三个数?
|
|
|
g****n
发帖数: 431 | 11 这是不对的。
只要需要找的数多于一个，总可以找到一种排列，使这些数按出现的顺序能彼此抵消，
最后他们的多数优
势被自己消耗掉了。所以这题没发办法直接转化成“一个数>1/2总数”的问题。
【在 g*******y 的大作中提到】
: 其实就是那个题：
: “有一个数出现的次数，>1/2*数组总个数，O(N)时间O(1)空间找出来”
: 的延伸而已
|
g*******y
发帖数: 1930 | 12 其实我觉得是可以的，maintain 3 slots，slot可以为空(对应counter为0即为空)
1：如果新来一个数，与某个slot中的数相同，该counter++
2: 否则，如果有空slot，填入；如果没有空slot，3个counter同时--
最终剩下的数，至少有一个是要找的数(没办法一趟就找齐3个数，但是扫描一趟能找出
3个数中的1个数已经
足够了)
严格的证明我还没想出来，不保证正确，欢迎反例或者补充证明。
ps，好久不做题了，呵呵，脑子快锈了
【在 g****n 的大作中提到】
: 这是不对的。
: 只要需要找的数多于一个，总可以找到一种排列，使这些数按出现的顺序能彼此抵消，
: 最后他们的多数优
: 势被自己消耗掉了。所以这题没发办法直接转化成“一个数>1/2总数”的问题。
|
g*******y
发帖数: 1930 | 13 我大概想了个粗糙的证明，大意就是考虑a b c d四个数，要求的答案是a，b，c。那么：
d的个数最少，必然不能存活到最后
考虑下面两种最坏的情况:
slots里面是: a,b,c，下一个数是d => 1个d干掉了1个a，1个b，1个c
slots里面是: d,a,b, 下一个数是c => 1个c干掉了1个d，1个a，1个b
这样，因为a,b,c的个数都比d多，d是无法笑到最后的。所以最后slots的数必然是abc
中的一个或多个
【在 g*******y 的大作中提到】
: 其实我觉得是可以的，maintain 3 slots，slot可以为空(对应counter为0即为空)
: 1：如果新来一个数，与某个slot中的数相同，该counter++
: 2: 否则，如果有空slot，填入；如果没有空slot，3个counter同时--
: 最终剩下的数，至少有一个是要找的数(没办法一趟就找齐3个数，但是扫描一趟能找出
: 3个数中的1个数已经
: 足够了)
: 严格的证明我还没想出来，不保证正确，欢迎反例或者补充证明。
: ps，好久不做题了，呵呵，脑子快锈了
|
s***e
发帖数: 793 | 14 基本是这样的
三个slot必须要maintain
每个slot存一个数，和它现在的score
如果新来一个数，没有free的slot,且不在slot里
其他所有slot， score --;
如果有数的score==0，free一个slot
如果数在3个slot里，这个slot 的 score += 3
其他occupied slot score--；
如果有富裕的，加一个新slot,score=3, 其他occupied slot score --；
【在 g*******y 的大作中提到】
: 其实我觉得是可以的，maintain 3 slots，slot可以为空(对应counter为0即为空)
: 1：如果新来一个数，与某个slot中的数相同，该counter++
: 2: 否则，如果有空slot，填入；如果没有空slot，3个counter同时--
: 最终剩下的数，至少有一个是要找的数(没办法一趟就找齐3个数，但是扫描一趟能找出
: 3个数中的1个数已经
: 足够了)
: 严格的证明我还没想出来，不保证正确，欢迎反例或者补充证明。
: ps，好久不做题了，呵呵，脑子快锈了
|
s***e
发帖数: 793 | 15 无聊，写了个code验证一下，基本work
void FindTop3(const std::vector & s)
{
int value[3];
int score[3];
score[0]=score[1]=score[2]=0;
int slotcount=3;
for(int i=0; i< s.size(); ++i)
{
int v = s[i];
int found=false;
for(int j = 0; j< 3; ++j)
{
if(score[j] > 0)
{
if(value[j] != v)
{
if(0 == --score[j] ) slotcount ++;
}
else
{
score[j] += 3;
found=true;
【在 g****n 的大作中提到】
: 这是不对的。
: 只要需要找的数多于一个，总可以找到一种排列，使这些数按出现的顺序能彼此抵消，
: 最后他们的多数优
: 势被自己消耗掉了。所以这题没发办法直接转化成“一个数>1/2总数”的问题。
|
m*****k
发帖数: 731 | |
