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快的（也就是找中位数
: ）
|
