重温matrix 1,真是神作 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Movie - 无限影话

重温matrix 1,真是神作

重温matrix 1,真是神作# Movie - 无限影话

B*p2017-10-21 07:10

1 楼

有个数组,其中三个数出现超过数组长度1/4, 怎么线性算法找出这三个数?

T*s2017-10-21 07:10

2 楼

直接放地里种不是更方便吗？

b*u2017-10-21 07:10

3 楼

二十年前的作品，涵盖当前热点：人工智能爆炸的危害，虚拟现实，新能源／生物
电池。希望我们的结局不会那么悲催。

r*o2017-10-21 07:10

4 楼

好像BlueAnt以前做过这题，呵呵。

【在 B*****p 的大作中提到】

: 有个数组,其中三个数出现超过数组长度1/4, 怎么线性算法找出这三个数?

l*n2017-10-21 07:10

5 楼

几个好处
保水保肥保温
还有就是不用深翻土

【在 T**********s 的大作中提到】

: 直接放地里种不是更方便吗？

b*u2017-10-21 07:10

6 楼

二十年前的作品，涵盖当前热点：人工智能爆炸的危害，虚拟现实，新能源／生物
电池。希望我们的结局不会那么悲催。

B*p2017-10-21 07:10

7 楼

有link吗?

【在 r****o 的大作中提到】

: 好像BlueAnt以前做过这题，呵呵。

C*g2017-10-21 07:10

8 楼

raised bed最大的好处，其实是不用担心杂草。
自然的地里，有着各种各样的杂草种子。种菜的过程就是和杂草斗争的过程。
raised bed最关键的一点就是只用买来的土，那是sterile的。
如果你用地里翻上来的土，那么raised bed一样要担心杂草，就毫无意义了。

d*p2017-10-21 07:10

9 楼

我们可能看不到结局了。但是matrix没有考虑人可能本身会改变成半生物半机器的物种
，还有人的智能和人工智能在人体的结合，也算一个遗漏吧。还有就是几乎所有这样的
科幻都假设机器，或者外星人，有一个中央控制，一旦关闭，或者停止指令，所有行动
都会终止。这无疑是另一个一厢情愿的假设。

l*c2017-10-21 07:10

10 楼

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, 怎么线性算法找出这三个数?

T*s2017-10-21 07:10

11 楼

那么这个raising bed放在什么地方呢？架在什么架子上或者放在阳台上？
即使用买来的土，直接放在地上还是会有杂草的顾忌的吧？因为离得太近啊？

【在 C*********g 的大作中提到】

: raised bed最大的好处，其实是不用担心杂草。
: 自然的地里，有着各种各样的杂草种子。种菜的过程就是和杂草斗争的过程。
: raised bed最关键的一点就是只用买来的土，那是sterile的。
: 如果你用地里翻上来的土，那么raised bed一样要担心杂草，就毫无意义了。

g*a2017-10-21 07:10

12 楼

类似于count sorting

t*x2017-10-21 07:10

13 楼

抬高之后还容易排水，植物根怕久泡水

【在 T**********s 的大作中提到】

: 直接放地里种不是更方便吗？

B*p2017-10-21 07:10

14 楼

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

T*s2017-10-21 07:10

15 楼

貌似这个东西就是边上一圈？低下空的啊？这怎么个弄法，还要另外买个底子么？
另外，怎么垫高？找砖头什么的？

【在 t*****x 的大作中提到】

: 抬高之后还容易排水，植物根怕久泡水

l*c2017-10-21 07:10

16 楼

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?

t*x2017-10-21 07:10

17 楼

raised之后不就比旁边的地高了吗？有个高度差就能排水啊
就是木头框把土筐起来
如果直接在地下种东西，农民也会挖陇，原理一样，高的地方种菜，低的沟方便排水

【在 T**********s 的大作中提到】

: 貌似这个东西就是边上一圈？低下空的啊？这怎么个弄法，还要另外买个底子么？
: 另外，怎么垫高？找砖头什么的？

I*g2017-10-21 07:10

18 楼

你问题问错了。应该是要求O(1)的空间吧

T*s2017-10-21 07:10

19 楼

绛紫。。。明白了！谢谢！
那这样也不是足够高啊，土里面的虫子还是会钻来钻去的不是？
另外大家都怎么施肥？
种子是直接撒在里面，还是用花盆育好了苗再移进去？

【在 t*****x 的大作中提到】

: raised之后不就比旁边的地高了吗？有个高度差就能排水啊
: 就是木头框把土筐起来
: 如果直接在地下种东西，农民也会挖陇，原理一样，高的地方种菜，低的沟方便排水

g*y2017-10-21 07:10

20 楼

其实就是那个题：
“有一个数出现的次数，>1/2*数组总个数，O(N)时间O(1)空间找出来”
的延伸而已

【在 B*****p 的大作中提到】

: 有个数组,其中三个数出现超过数组长度1/4, 怎么线性算法找出这三个数?

t*x2017-10-21 07:10

21 楼

施肥我不知道，育苗是个专题，你搜索一下版内吧。多数是先发好苗再种到地里

【在 T**********s 的大作中提到】

: 绛紫。。。明白了！谢谢！
: 那这样也不是足够高啊，土里面的虫子还是会钻来钻去的不是？
: 另外大家都怎么施肥？
: 种子是直接撒在里面，还是用花盆育好了苗再移进去？

s*a2017-10-21 07:10

22 楼

让我想起了编程之美的发贴水王

【在 B*****p 的大作中提到】

: 有个数组,其中三个数出现超过数组长度1/4, 怎么线性算法找出这三个数?

l*u2017-10-21 07:10

23 楼

省水省肥，易于管理，一堆的好处。

【在 t*****x 的大作中提到】

: 施肥我不知道，育苗是个专题，你搜索一下版内吧。多数是先发好苗再种到地里

g*n2017-10-21 07:10

24 楼

这是不对的。
只要需要找的数多于一个，总可以找到一种排列，使这些数按出现的顺序能彼此抵消，
最后他们的多数优
势被自己消耗掉了。所以这题没发办法直接转化成“一个数>1/2总数”的问题。

【在 g*******y 的大作中提到】

: 其实就是那个题：
: “有一个数出现的次数，>1/2*数组总个数，O(N)时间O(1)空间找出来”
: 的延伸而已

a*a2017-10-21 07:10

25 楼

还可以用不同种类的泥／沙，灵活性大

g*y2017-10-21 07:10

26 楼

其实我觉得是可以的，maintain 3 slots，slot可以为空(对应counter为0即为空)
1：如果新来一个数，与某个slot中的数相同，该counter++
2: 否则，如果有空slot，填入；如果没有空slot，3个counter同时--
最终剩下的数，至少有一个是要找的数(没办法一趟就找齐3个数，但是扫描一趟能找出
3个数中的1个数已经
足够了)
严格的证明我还没想出来，不保证正确，欢迎反例或者补充证明。
ps，好久不做题了，呵呵，脑子快锈了

【在 g****n 的大作中提到】

: 这是不对的。
: 只要需要找的数多于一个，总可以找到一种排列，使这些数按出现的顺序能彼此抵消，
: 最后他们的多数优
: 势被自己消耗掉了。所以这题没发办法直接转化成“一个数>1/2总数”的问题。

g*y2017-10-21 07:10

27 楼

我大概想了个粗糙的证明，大意就是考虑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*e2017-10-21 07:10

28 楼

基本是这样的
三个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 的大作中提到】

s*e2017-10-21 07:10

29 楼

无聊，写了个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 的大作中提到】