c++ - 更有效的方法来计算一个时间间隔内的值数量？

我想确定在每个给定的间隔(很多)中有多少个输入数组(最多50000个)。

当前，我正在尝试使用此算法来执行此操作，但是它太慢了:

范例数组:{-3、10、5、4，-999999、999999、6000}
示例间隔:[0，11](包括)

排序数组-O(n * log(n))。 (-999999，-3、4、5、10、6000、999999)

查找min_index: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)复杂度。有待改善？一点也不。为什么？因为问题等同于排序。众所周知，不可能获得更好的计算复杂度。 (通过比较进行排序。)