作者Leon (Achilles)
站内Prob_Solve
标题Re: [问题] Google Interview Question (2)
时间Thu Feb 14 11:33:32 2013
※ 引述《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.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 142.136.127.112
1F：推 RockLee:其实这正是F大及P大点出可以改进的地方 以所举的case为例 02/14 11:41
2F：→ RockLee:第一次先拿 34 跟 14 16 18 28 30 32 比 就知道第二次拿 02/14 11:42
3F：→ RockLee:34 跟 XX XX XX (upper-right) 29 31 33 比即可 02/14 11:42
4F：→ Leon:我看不懂你写甚麽 02/14 11:48
5F：推 RockLee:意思是虽然 upper-right and lower-left 共有 18 elements 02/14 11:54
6F：→ RockLee:但其实 pivort 只需和其中 12 elements 比即可知道 rank 02/14 11:54
7F：→ Leon:write a articule and I will take a look after dinner 02/14 11:55
8F：→ RockLee:方法是先和 medians of upper-right and lower-left 比 02/14 11:55
9F：→ RockLee:例如 34 跟 14 比过之後就知道不需要跟 13 比了 02/14 11:55
10F：→ RockLee:不好意思推完才发现L大希望我回文 02/14 11:58
11F：→ Leon:你的方法应该不对, 你写篇 detail 的作法 02/14 15:30
12F：推 RockLee:不好意思 L大可以指出哪个部分有误或不够detail吗? 02/14 16:28
13F：推 yoco315:我也想看 Leon 大大的详解 XD 02/16 13:19