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 | |