给定n个硬币(其中一些较重),使用O(log ^ 2 n)权重查找重硬币数量的算法。请注意,所有重硬币的重量均相同,所有轻硬币的重量也相同。
您将获得一个天平,通过它可以比较两个不相交的硬币子集的权重。请注意,余额仅指示哪个子集较重,或者它们是否具有相等的权重,而不是绝对权重。
我不会给出完整的答案,但是我会帮助您细分的。
O(log(n))
提示:
O(log^2(n))