gpt4 book ai didi

c++ - 计算间隔内值数量的更有效方法?

转载 作者:太空狗 更新时间:2023-10-29 20:39:49 24 4
gpt4 key购买 nike

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

目前,我正在尝试用这个算法来做,但它太慢了:

示例数组:{-3, 10, 5, 4, -999999, 999999, 6000}
示例间隔:[0, 11](含)

  1. 排序数组 - O(n * log(n)) . (-999999, -3, 4, 5, 10, 6000, 999999)
  2. 找到最小索引:array[min_index] >= 0 - O(n) . (对于我的示例,min_index == 2)。
  3. 找到 max_index:array[max_index] <= 11 - O(n) . (对于我的示例,max_index == 4)。
  4. 如果两个索引都存在,那么Result == right_index - left_index + 1 (对于我的示例,结果 = (4 - 2 + 1) = 3)。

最佳答案

你的想法不错,但需要修改。您应该使用 binary searchO(lg n) 时间内找到间隔的开始和结束.如果 n 是数组的长度并且 q 是问题的数量 [a, b] 你有 O(n+q*n) 时间,使用二进制搜索它是 O((n + q) lg n)(来自排序数组的n lg n)。这个解决方案的优点是简单,因为 C++ 有 std::lower_boundstd::upper_bound .你可以使用 std::distance .这只是几行代码。

如果 q 等于 n,则此算法的复杂度为 O(n lg n)。有待改善?一点也不。为什么?因为这个问题相当于排序。众所周知,不可能获得更好的计算复杂度。 (比较排序。)

关于c++ - 计算间隔内值数量的更有效方法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26496219/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com