如果我有一个二维数组(2 列，10000 行，如下例)，其中第一列是一些数值，第二列是一个指示符(1 或 0)。什么是有史以来最有效的算法(就计算速度而言)来计算 2 个数值之间 1 的数量，例如 200 到 800 之间？ 二维数组示例:
#2A((315 1)
(1941 1)
(1914 0)
(970 1)
(1600 0)
(283 0)
(843 0)
(1831 1)
(1584 1)
(1918 1)
...)
最佳答案
方法一
如果你只想执行一次操作，那么你不能比 O(n) 做得更好，因为你需要至少检查每个条目一次:
for each item
if low<=item[0]<=high and item[1]==1:
count += 1
方法二
如果您想执行多个查询，那么一种方法是丢弃所有带 0 的项目，对剩余的项目进行排序，然后对于每个查询使用二分法查找给定范围内的项目数。
这将是 O(nlogn) 的排序(这只需要完成一次)加上每个查询的 O(logn)。
方法三
如果你的数字在长度 B 的固定范围内，那么你可以设置一个数组，其中包含每个 bin 中有多少项(值为 1)，然后计算该数组的累积和。
这将给出 O(n+B) 的预处理时间，加上每个查询的 O(1)
关于arrays - 二维数组的计数算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21906042/