※ 引述《RockLee (Now of all times)》之銘言：
: ※ 引述《Leon (Achilles)》之銘言：
: : 你每次用 median of median, 幹掉某個比例的 element,
: : 很快就找到了.
: : 你參照一下
: : http://stackoverflow.com/questions/4075289/race-car-puzzle
: : 看
: : answered Mar 9 '11 at 22:59
: : Tom Sirgedas
: : 的答案, 我沒有去 trace 每一步, 但大致上應該是對的.
: 我明白 median of medians 可以每次幹掉某個比例的 elements
: 但重點是所謂的 "很快就找到了" 到底有多快呢?
: Tom Sirgedas 說他的解法需要 17 次
: 而我之前貼的網站的解法經 F 大及 P 大點出可以改進的地方後
: 看來只需要 16 次 所以目前看來最佳解是 16 次
小弟 (或是大哥?) 我不太喜歡幫人 trace code,
不過你這個簡直是得太明顯了
: 那個網站的解法基本上也是在幹掉某個比例的 elements
: 以下是將該網站的解法修正後16次的版本
: 如果有錯誤或還可以改進的地方再麻煩指出了:
: Step A (Find the rank of the median of medians):
: (7 races) Divide the cars into 7 groups and get the order within each group.
: (1 race) Take the 7 medians and get the order. Find the median of medians
: (denote as o). In following example, it is 34.
下面這一步, upper-right and lower-left 共有 18 elements,
你怎麼用 2 races 就和 pivort 比出來?
: (2 races) Find the rank of the median of medians. Take 6 elements from
: lower-left corner and upper-right corner and race against the o.
: After 2 rounds, we know the rank of this median of medians within
: in the whole set.
: The best case is that o is the global median (25th fastest).
: The worst case is that o is the 16th or 34th fastest.
: Example:
: 1 2 3 4 13 14 XX <- group 1
: 5 6 7 8 15 16 XX <- group 2
: 9 10 11 12 17 18 XX <- group 3
: 19 20 XX 34 35 36 37 <- group 4
: XX 28 29 38 39 40 41 <- group 5
: XX 30 31 42 43 44 45 <- group 6
: XX 32 33 46 47 48 49 <- group 7
: (XX: 21 ~ 27)
: Step B (We want to find the rank of other medians in a binary search fashion):
: (2 races) Pick the median less than 34, which is 12.
: Race it against the lower-left and upper-right corner cars.
: After 2 races, we know its rank is 12.
: Now, the gap between those two medians are at most 21,
: as shown in this example.
: Rearrange the 21 cars (>12 and <34) as follows:
: 13 14 XX <- group 1
: 15 16 XX <- group 2
: 17 18 XX <- group 3
: 19 20 XX <- group 4
: XX 28 29 <- group 5
: XX 30 31 <- group 6
: XX 32 33 <- group 7
: Step C
: (1 race) Find the median of medians again, which is 20.
: (1 race) Find its rank.
: After this step, we know the car in previous step is ranked 20.
: (1 race) Similar to step A, check the rank of another median, 28.
: (1 race) Sort all cars between 21 ~ 27. The 25th fastest car is found.