我想确定输入数组(最多 50000)中的每个给定间隔(很多)中有多少个数字。
目前，我正在尝试用这个算法来做，但它太慢了:
示例数组:{-3, 10, 5, 4, -999999, 999999, 6000}
示例间隔:[0, 11](含)
- 排序数组 -
O(n * log(n)). (-999999, -3, 4, 5, 10, 6000, 999999) - 找到最小索引:
array[min_index] >= 0-O(n). (对于我的示例，min_index == 2)。 - 找到 max_index:
array[max_index] <= 11-O(n). (对于我的示例，max_index == 4)。 - 如果两个索引都存在，那么
Result == right_index - left_index + 1(对于我的示例，结果 = (4 - 2 + 1) = 3)。
最佳答案
你的想法不错，但需要修改。您应该使用 binary search 在 O(lg n) 时间内找到间隔的开始和结束.如果 n 是数组的长度并且 q 是问题的数量 [a, b] 你有 O(n+q*n) 时间，使用二进制搜索它是 O((n + q) lg n)(来自排序数组的n lg n)。
这个解决方案的优点是简单，因为 C++ 有 std::lower_bound和 std::upper_bound .你可以使用 std::distance .这只是几行代码。
如果 q 等于 n，则此算法的复杂度为 O(n lg n)。有待改善？一点也不。为什么？因为这个问题相当于排序。众所周知，不可能获得更好的计算复杂度。 (比较排序。)
关于c++ - 计算间隔内值数量的更有效方法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26496219/