c++ - 如何在假币算法中称重

Question

我正在尝试为假币问题开发 C++ 代码。我正在使用一个二进制数组 n long 填充 1 和一个随机的 0 来表示假硬币。当我将数组分成两半以比较权重时，我该如何确定每一侧的权重？

我可以很容易地计算每个数组中 1 的数量，但这将是一个线性运行时间。整个算法应该是次线性的。

有没有办法在常数时间内确定每个数组的权重？

披露:这是一项学校作业，因此希望您能在不给出完整答案的情况下给出提示。

Answer 1

作为一名学生，我会坚持这一点，因为您计算了每 半场 中 1 的数量，并且您正在有效地使用这种方法:

Decrease-and-Conquer

结果，您实际上称重了 O(log₂ n) 次，这使得算法是次线性的。

我的观点是，优化算法的是您执行的称重次数及其有效空间(一半与全部)。

在此 CS session 中阅读更多内容，建议如果你在 3 处拆分，你可以做得更好并实现 O(log₃ n)。但是，如果您是新手，现在分成两半就好了! =)

---

如果您想尝试一些代码，可以使用 std::bitset , 它提供了 count() ，返回位集中 1 的数量。