二维阵列的计数算法
二维阵列的计数算法
提问于 2014-02-20 11:14:19
如果我有一个2D数组(2列，10000行，下面的例子)，其中第一列是一些数值，第二列是指示符(1或0)。在计算速度方面，最有效的算法是在两个数值之间计算1的数目，例如200到800？2D数组示例：
#2A((315 1)
(1941 1)
(1914 0)
(970 1)
(1600 0)
(283 0)
(843 0)
(1831 1)
(1584 1)
(1918 1)
...)回答 2
Stack Overflow用户
回答已采纳
发布于 2014-02-20 11:22:22
方法1
如果您只想执行一次操作，那么您就不能比O(n)做得更好，因为您需要检查每个条目至少一次：
for each item
if low<=item[0]<=high and item[1]==1:
count += 1方法2
如果要执行多个查询，那么一种方法是丢弃所有0的项，对其余的项进行排序，然后对每个查询使用二分法来查找给定范围内的项目数。
这将是排序的O(nlogn) (只需要执行一次)加上每个查询的O(logn)。
方法3
如果您的数字在一个固定的B长度范围内，那么您可以设置一个数组，其中包含在每个bin中有多少项(值为1)，然后计算该数组的累积和。
这将为每个查询提供一个O(n+B)预处理时间加上O(1)。
Stack Overflow用户
发布于 2014-02-20 11:21:05
如果您的数组没有排序，那么除了对数组的每一对(a，b)进行检查(a，b)是否在界内和b= 1之外，您什么也做不了。这显然是一个O(n)算法。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/21906042
复制相关文章
相似问题
腾讯云开发者
