作者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)