一尘不染

给定n个硬币(其中一些较重),找到重硬币的数量吗?

algorithm

给定n个硬币(其中一些较重),使用O(log ^ 2 n)权重查找重硬币数量的算法。请注意,所有重硬币的重量均相同,所有轻硬币的重量也相同。

您将获得一个天平,通过它可以比较两个不相交的硬币子集的权重。请注意,余额仅指示哪个子集较重,或者它们是否具有相等的权重,而不是绝对权重。


阅读 239

收藏
2020-07-28

共1个答案

一尘不染

我不会给出完整的答案,但是我会帮助您细分的。

  1. 找到一种O(log(n))算法来查找单个沉重的硬币。
  2. 找到一种O(log(n))算法,将一个集合分为两个集合,分别具有相同数量的重计数和轻计数,以及最多两个剩余数(用于每个数均不存在的情况)。
  3. 结合算法1和2。

提示:

  • 算法#1独立于算法#2。
  • O(log(n)) 提示二进制搜索
  • 您可能最终会O(log^2(n))得到两种O(log(n))算法?
2020-07-28