刚才面试问到的一个问题,太菜没想出,求教各位?

有100个电池,一次只能测两个电池的电量,如何测才能最少次数找出电量最少的两个电池?不是排序T^T
全部评论
我的方法是对5楼的说明补充,已经补充在他的楼下了。类似的题就是25匹马,5赛道找3个最快的马一样的方法
点赞
送花
回复
分享
发布于 2018-09-05 22:20
就是基于比较的top1,top2同时求的问题。算法导论的求顺序统计量那里有。需要3/2n取下整。
点赞
送花
回复
分享
发布于 2018-09-05 23:23
滴滴
校招火热招聘中
官网直投
二分法
点赞
送花
回复
分享
发布于 2018-09-05 20:23
topk算法?Priority queue?
点赞
送花
回复
分享
发布于 2018-09-05 20:26
这个测试是只能比较两两的大小吗?如果可以记录数值的话,全部测一遍不就行了
点赞
送花
回复
分享
发布于 2018-09-05 20:28
回答了TOPK 他说不是排序,不懂啥意思
点赞
送花
回复
分享
发布于 2018-09-05 20:38
分成50组,测50次,得出较少的50个电池,在分成25组,测25次,得出较少的25个电池……这样重复吧_(:3」∠)_
点赞
送花
回复
分享
发布于 2018-09-05 20:53
先比较n-1找最大,再比较log2(n)-1次找次大。
点赞
送花
回复
分享
发布于 2018-09-05 22:08
我算出来需要105次,应该是最少的了
点赞
送花
回复
分享
发布于 2018-09-05 22:31
随意一个A当做最小,然后比较,找出比他小的B并且标记A,B,然后继续向后比较,得到比B小的,同时取消A的标记,...直到遍历完成
点赞
送花
回复
分享
发布于 2018-09-06 00:15
难道不是50次么。。。12/34/56/78/...记录最小电量电池就行了
点赞
送花
回复
分享
发布于 2018-09-06 10:04
我算出来是100次,应该是最少的了
点赞
送花
回复
分享
发布于 2018-09-07 23:52

相关推荐

点赞 20 评论
分享
牛客网
牛客企业服务