作者查詢 / fadingaway

總覽項目：發文 | 留言 | 暱稱

作者 fadingaway 在 PTT [ Prob_Solve ] 看板的留言(推文), 共9則

限定看板：Prob_Solve

首頁

尾頁

[ Prob_Solve ]7 留言, 推噓總分: +2

作者: colorflags - 發表於 2010/06/29 09:41(15年前)

1^F推fadingaway:第二個方法應該就是正解，因為題目保證眾數會超過一半06/29 11:32

2^F→fadingaway:即使剛好一半，也可以在小修正後得到linear-time的結果06/29 11:33

5^F推fadingaway:我是在一次演講聽到的，結果可以推到眾數佔1/k比例以上06/29 23:11

6^F→fadingaway:http://tinyurl.com/282bk2v 這是該次演講的類似投影片06/29 23:12

7^F→fadingaway:你可以參考第39頁 (k-iceberg)06/29 23:12

[ Prob_Solve ]6 留言, 推噓總分: +3

作者: colorflags - 發表於 2010/06/28 12:39(15年前)

5^F推fadingaway:這個問題在comparison model下有Ω(nlgn)的lower bound06/28 18:58

6^F→fadingaway:參考: element uniqueness problem06/28 18:58

[ Prob_Solve ]3 留言, 推噓總分: +2

作者: mqazz1 - 發表於 2010/04/30 21:03(15年前)

2^F推fadingaway:你算錯了，encode 0 ~ n^2-1 的整數只需要 2*lg n bits05/01 00:35

3^F推fadingaway:r 是給你自己任意代入的正整數, 1 <= r <= b05/01 13:41

首頁

尾頁