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