※ 引述《Leon (Achilles)》之銘言：
: : 推 RockLee:不好意思不是很懂L大的意思 Third round拿X跟2 unkonws比 02/13 15:52
: : → RockLee:就可以知道5th嗎? 以下123與ABC的情形要如何區分呢? 02/13 15:52
: : → RockLee:(game 1) 1 2 9 (game A) 1 2 7 02/13 15:52
: : → RockLee:(game 2) 3 4 5 (game B) 3 4 6 02/13 15:52
: : → RockLee:(game 3) 6 7 8 (game C) 5 8 9 02/13 15:53
:
我留你的例子和下面寫的東西.
你需要去加強分析的概念, 以及 Quick sort Pivot 的使用.
如果你用上面 Game (1,2,3) 的例子, 以及照你的定義
號碼代表車子真正的速度
那麼, median of median 這一步
是拿 cars 2,4,7 來比.
此時 median of median 是 4.
把這個當作 Pivort, 可以保證
2 < 4, and 1 < 2 from step 1.
and 3 < 4 from step 1.
所以我得到 (1,2,3) 比 car 4 快,
以及 (5,7,8) 比 4 慢.
但 (6, 9) 此時是 unknown.
這個題目 scale 比較小, 所以下一步會是比
(4,6,9)
然後我就可以知道,
(1,2,3) 比 4 快,
(6), (9), (5), (7,8) 比 4 慢.
用這個 Pivort, 我找到了前四個 element (順序不明),
此時要找第五個, 會在 6,9,5 之間產生.
你每次用 median of median, 幹掉某個比例的 element,
很快就找到了.
你參照一下
http://stackoverflow.com/questions/4075289/race-car-puzzle
看
answered Mar 9 '11 at 22:59
Tom Sirgedas
的答案, 我沒有去 trace 每一步, 但大致上應該是對的.
: