提问人：Gulzar 提问时间：6/30/2022 最后编辑：Gulzar 更新时间：6/30/2022 访问量：284
给定一个未排序的二进制数组，计数 1 的数量，其中只允许检查整个子数组是否全部为零
Given an unsorted binary array, count number of 1's, where allowed only to check if an entire subarray is all zeros
问：
给定一个未排序的二进制数组，唯一允许的操作是 ，当数组的所有元素均为 0 时，它将返回 。
其复杂性在于aall_zeros(a)Trueall_zeros(a)o(len(a)) + large overhead constant
我想找到所有包含 1 的索引，尽可能少地运行 all_zeros 一个合理的子问题是假设 1 的数量比 0 的数量“小得多”（比如 x100~x1000）。
从理论上讲，这可以通过迭代数组元素并测试来解决。
在实践中，开销常数迫使我们尽可能大批量地工作。我们不能假设知道数组中 1 的比率，但如果某些算法需要该知识，请分享它。all_zeros([element])
我正在寻找一个概念性的解决方案，因此我没有指定开销常数与计算时间之间的比率。all_zeros
请注意，我正在寻找一个普通情况的解决方案，而不是一个最坏的情况解决方案。
现在需要定义 1 和 0 的概率分布，但我试图将其保持在较高水平，我不会深入探讨细节，同时仍然保持可回答性。
可能有一个最好的解决方案，它总是能获得最小的开销。如果有，它将被接受。
答：
1赞
MrSmith42
6/30/2022
#1
我会检查大块，如果它们不为零，我只尝试较小的块。 根据 1 秒和“大开销常数”的比率，我会选择合适的起始尺寸。
这里是如何检查的想法（通过示例）
数据：（空格仅用于可读性）
00001110 00100001 00100000 01000000 00000000 00000000 00000101 01010000
1. xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
-> both checked intervalls are non-zero -> half them
2. xxxxxxxxxxxxxxxxx XXXXXXXXXXXXXXXXX xxxxxxxxxxxxxxxxx XXXXXXXXXXXXXXXXX
non-zero non-zero zero non-zero
3. xxxxxxxx XXXXXXXX xxxxxxxx XXXXXXXX xxxxxxxx XXXXXXXX
n-z n-z n-z n-z n-z n-z
4. xxxxXXXX xxxxXXXX xxxxXXXX xxxxXXXX xxxxXXXX xxxxXXXX
zero n-z n-z n-z n-z zero n-z zero zero n-z n-z zero
5. xxXX xxXXxxXX xxXX xxXX xxXX xxXX
...
我希望这个想法是明确的。但我强烈建议分析从哪个块大小开始，以及何时切换为单元素块。
0赞
Matt Timmermans
6/30/2022
#2
如果某个子数组返回 false，则可以在该子数组中进行二进制搜索以查找第一个 1 的位置。此过程不会告诉您有关该 1 之后的任何元素的信息，因此您将在那之后重新开始。all_zeros(a)
问题是进行初始查询的大小。如果每个查询返回 true 的概率为 50%，则查询总数最少。如果初始查询有 50% 的几率找到 1，那么二叉搜索中的所有查询也将有 50% 的几率，如果 1 平均相隔 L 个槽，则每 1 的总成本是对数2 L + 1 个查询。
如果 L 的长度是它应该的两倍，或者是它应该长度的一半，那么每 1 个查询的成本就会增加大约 1 个，当 1 个相距很远时，这是一个相当小的代价。
因此，一个不需要知道 1 的频率就可以开始的非常好的算法是：
- 比如说，设置 L=128。这是对 1 个频率的先验估计。
- 检查前 L 个元素。如果全部为零，则将 L 乘以 2 并继续数组的其余部分。
- 否则，如果 L > 1，则将 L 除以 2，二进制搜索以找到第一个 1 的位置，然后在第一个 1 之后继续数组的其余部分。
如果 1 是随机分布的，则总成本将是每 1 个查询的日志2 L + some_small_number，我认为这是最坏的情况。
评论
all_zero1