※ 引述《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 每一步, 但大致上应该是对的.
: