作者RockLee (Now of all times)
看板Prob_Solve
標題Re: [問題] Google Interview Question (2)
時間Thu Feb 14 11:04:24 2013
※ 引述《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 次
那個網站的解法基本上也是在幹掉某個比例的 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.
(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.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.252.88.12
※ 編輯: RockLee 來自: 111.252.88.12 (02/14 11:18)