PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] Google Interview Question (2)

看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間11年前 (2013/02/14 11:33)推噓4(4推 0噓 9→)

留言13則, 3人參與討論串6/9 (看更多)

※ 引述《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