c******n
发帖数: 4965 | 1 25 horses, you can race 5 of them at a time to find our the relative speed
order,
how many races do you need to find the 12 fastest ?
now I realize it's just the guaranteed linear time median selection alg.
http://www.careercup.com/question?id=4280852 |
i**9
发帖数: 351 | |
P********l
发帖数: 452 | 3 This question is very classic.
Here is what I have:
http://www.sureinterview.com/shwqst/1062001/154001
Any better idea? |
g*********s
发帖数: 1782 | 4 interesting observation.
if so clrs should use this example.
speed
【在 c******n 的大作中提到】
: 25 horses, you can race 5 of them at a time to find our the relative speed
: order,
: how many races do you need to find the 12 fastest ?
: now I realize it's just the guaranteed linear time median selection alg.
: http://www.careercup.com/question?id=4280852
|
g*****k
发帖数: 623 | 5 I believe that the solution is wrong.
If you use median select algorithm, you only know
the median of the medians is a good pivot value, where you know
values in upper-left part are smaller than the median of the medians
and values in bottom-right part are bigger than the median of the medians.
But you dont know the exact order among them. So the X-th element could be
anywhere, such as it could be in the upper-left part or in the bottom right
....
This approach is interesting though.
【在 P********l 的大作中提到】
: This question is very classic.
: Here is what I have:
: http://www.sureinterview.com/shwqst/1062001/154001
: Any better idea?
|
s***n
发帖数: 459 | 6 idea是一样的,加一点后期处理而已.
right
【在 g*****k 的大作中提到】
: I believe that the solution is wrong.
: If you use median select algorithm, you only know
: the median of the medians is a good pivot value, where you know
: values in upper-left part are smaller than the median of the medians
: and values in bottom-right part are bigger than the median of the medians.
: But you dont know the exact order among them. So the X-th element could be
: anywhere, such as it could be in the upper-left part or in the bottom right
: ....
: This approach is interesting though.
|
P********l
发帖数: 452 | 7 I found the solution was incorrect right after I posted it, so I grayed it
out.
Why not GET some feedBACK there if you have some idea? SureInterview is just
my hobby website without any commercial background. There is nothing to
worry about.
right
【在 g*****k 的大作中提到】
: I believe that the solution is wrong.
: If you use median select algorithm, you only know
: the median of the medians is a good pivot value, where you know
: values in upper-left part are smaller than the median of the medians
: and values in bottom-right part are bigger than the median of the medians.
: But you dont know the exact order among them. So the X-th element could be
: anywhere, such as it could be in the upper-left part or in the bottom right
: ....
: This approach is interesting though.
|
c**********6
发帖数: 105 | |
g*****k
发帖数: 623 | 9 Hehe, sure!
Marked already
just
【在 P********l 的大作中提到】
: I found the solution was incorrect right after I posted it, so I grayed it
: out.
: Why not GET some feedBACK there if you have some idea? SureInterview is just
: my hobby website without any commercial background. There is nothing to
: worry about.
:
: right
|
P********l
发帖数: 452 | |
|
|
p***l
发帖数: 586 | 11 我觉得
第一次7 races过后让最差的7个比一次，找median，这样前21就确定了。最后从剩下四
个组的第一名里面再比一次找第四名不久OK了么？这样只需要比7+1+1次
【在 P********l 的大作中提到】
: 更新了. 看看这回对不对？
: http://www.sureinterview.com/shwqst/1062001/154001
|
P********l
发帖数: 452 | 12 反例:
43 x x x x x x <- group 1
44 x x x x x x
45 x x x x x x
46 x x x x x x
47 25 x x x x x
48 x x x x x x
49 x x x x x x
49最差, x 随便填 |
a*******1
发帖数: 1554 | 13 Hello，整体思路大概明白，确实很牛B，我原来的方法要34次。。。。。。
有几点不明白：
Round Two里
2.(1 race) Get the median of medians again.
+ + + + + <- new group 1
+ + + + l l l <- new group 2
- - - l l l l <- group 5
- - - l l l l <- group 6
- - - l l l l <- group 7
但中间的那个l要与两组左小角-右上角对比：
- - - l + +
- - - l l l l
应该是两次吧
另外，这时是33个里头选第9快（s表示快，l表示慢），由于9靠近33的前部分，所以此
时用中间来划分未必最优，比如
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31 32 33
如果选16来分，最差情况是21匹马选第9快的，部分已排序；但如果此时选15的话，先
比左下-右上这两次：
20 21 15 3 4 5
27 28 15 9 10 11 12
如果都比15号马大（即速度更慢，更倾向于l），则15是第8快，第9块就是余下那些里
头最快的，故（20，27，16，23，30，3，9）赛一下取最快就行，甚至可以利用前面结
果不用那么多马来比，只用1次；
最麻烦是其他都比15号马快，则有18个比它快，第9快的也在这里头，18选9
，部分已排序，随后我算过只需4次。
不知道有没说清楚。。。。。。
【在 P********l 的大作中提到】
: 反例:
: 43 x x x x x x <- group 1
: 44 x x x x x x
: 45 x x x x x x
: 46 x x x x x x
: 47 25 x x x x x
: 48 x x x x x x
: 49 x x x x x x
: 49最差, x 随便填
|
z**k
发帖数: 629 | 14 26次?
先用经典方法三次(9+8+7次)找到前9后9.再用2次在7匹中选3匹.总计9+8+7+2=26次. |
P********l
发帖数: 452 | 15 展开说说？
【在 z**k 的大作中提到】
: 26次?
: 先用经典方法三次(9+8+7次)找到前9后9.再用2次在7匹中选3匹.总计9+8+7+2=26次.
|
P********l
发帖数: 452 | 16 确实要两次。你后面的分析也对，但是总的来说这个方法不太容易说清楚。
我又加了一种方法(solution 1)，比较容易理解一些。
http://www.sureinterview.com/shwqst/1062001/154001
Round one
1. (7 races) Divide the cars into 7 groups and get the order within each
group.
2. (1 race) Take the 7 medians and sort them. Find the median of medians
(denote as o). In following example, it is 34.
3. (3 races) Find the rank of the median of medians. Take 6 elements from
lower-left corner (25 ~ 33) and upper-right corner (13 ~ 21) and race
against the o (34). After 3 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.
The following example shows one possible worst case.
1 2 3 4 13 14 15 <- group 1
5 6 7 8 16 17 18
9 10 11 12 19 20 21 ...
22 23 24 34 35 36 37
25 26 27 38 39 40 41 <- group 5
28 29 30 42 43 44 45 <- group 6
31 32 33 46 47 48 49 <- group 7
Round two
We want to find the rank of other medians.
1. (3 races) Pick the median less than 34, which is 12. Race it against
the lower-left and upper-right corner cars. After 3 races, we know its rank
is 12.
Now, the gap between those two medians are at most 21, as shown in this
example.
Round three
Rearrange the 21 cars as follows.
13 14 15 <- group 1
16 17 18
19 20 21 ...
22 23 24
25 26 27 <- group 5
28 29 30 <- group 6
31 32 33 <- group 7
Each lines are still sorted.
1. (1 race) Find the median of medians again, which is 23.
2. (1 race) Find it rank. After this step, we know the car in previous
step is ranked 23 for sure.
3. (1 race) Similar to a binary search, check the rank of another median,
29.
4. (1 race) Sort all cars between 23 ~ 29. The 25th fastest car was found.
So at most 18 races are needed to get the 25th fastest car.
【在 a*******1 的大作中提到】
: Hello，整体思路大概明白，确实很牛B，我原来的方法要34次。。。。。。
: 有几点不明白：
: Round Two里
: 2.(1 race) Get the median of medians again.
: + + + + + <- new group 1
: + + + + l l l <- new group 2
: - - - l l l l <- group 5
: - - - l l l l <- group 6
: - - - l l l l <- group 7
: 但中间的那个l要与两组左小角-右上角对比：
|
