使用中位数的N硬币中最轻和最重的硬币
假设有一个中位尺度的输入三枚硬币，并在三枚硬币中返回中位数，它不会说明两枚硬币的其余部分。我们如何使用O（NLGN）在硬币中最轻，最重。提供了n个不同的硬币。
Suppose there is a median scale which takes an input of three coins and returns the median among three coins, it won't tell anything about the rest of two coins. How can we find the lightest and heaviest among the coins using O(nlgn).Provided there are n distinct coins.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
最轻，最重的硬币是唯一不是任何群体中位数的硬币。
选择任何3个硬币，然后丢弃中位数。重复直到剩下2个。
由于每个操作都会丢弃硬币，因此需要O（n）时间。
The lightest and heaviest coins are the only ones that aren't the median of any group.
Pick any 3 coins and discard the median. Repeat until there are only 2 left.
Since each operation discards a coin, this takes O(n) time.