l*******l 发帖数: 248 | 1 老题了,49匹马,7个轨道,不能计时,要比多少次能找到第25快的(也就是找中位数
) |
r*******y 发帖数: 1081 | 2 这种题目要是5分钟内把答案给出来了,面试官会相信是自己想出来的吗
【在 l*******l 的大作中提到】 : 老题了,49匹马,7个轨道,不能计时,要比多少次能找到第25快的(也就是找中位数 : )
|
l*******l 发帖数: 248 | 3 我明白你的意思。。。我看过几个版本的solution,都有道理,想知道哪个是对的而已。
【在 r*******y 的大作中提到】 : 这种题目要是5分钟内把答案给出来了,面试官会相信是自己想出来的吗
|
m*********g 发帖数: 646 | |
a****i 发帖数: 108 | 5 给个答案的link吧,多谢
已。
【在 l*******l 的大作中提到】 : 我明白你的意思。。。我看过几个版本的solution,都有道理,想知道哪个是对的而已。
|
p***o 发帖数: 3399 | |
A********e 发帖数: 242 | |
s*******0 发帖数: 3461 | |
c*********g 发帖数: 37 | 9 如果7个轨道都分开的话
假设每个轨道都是7匹马(不确定1)
把一个轨道堪称一个数组的话
因为排在前面的马就是速度快的马
所以找到每个轨道的中位数只要做数组读取就可以了不用比较(不确定2)
然后再比较7个中位数 找到中位数
这里需要7次比较 用order-statistics的算法
worse-case需要linear time
所以就需要7次比较
不知道这个分析对不对
【在 l*******l 的大作中提到】 : 老题了,49匹马,7个轨道,不能计时,要比多少次能找到第25快的(也就是找中位数 : )
|