什么是查找排序范围内元素数量的最快方法？

鉴于排序列表
1, 3, 5, 6, 9....
是否有一个快速的算法，而不是O(n)计算给定范围内[a, b]元素的数量，假设所有的数字都是整数？什么是查找排序范围内元素数量的最快方法？

来源

2013-02-07 Chan

哪种语言？ – sgarizvi

我很好用C/C++，Java或C＃。会把语言标签。提前致谢。 – Chan

'std :: lower_bound'和'std :: upper_bound'？给你比你要求的更多... – Mehrdad

这是一个O（log n）算法：使用binary search搜索两个端点，那么范围内的元素数量基本上就是指数的差异。

为了得到一个需要区分其中该范围的端点是阵列中与否的情况下的具体数量。

来源

2013-02-07 06:40:09 Henry

你需要走差异化加一？我认为这是关闭的。 – templatetypedef

@templatetypedef可能是的，有几种情况取决于端点是否实际存在于数组中。 – Henry

也假定数据结构是可索引的。例如，如果排序的数据结构是链接列表或树，则不存在索引。 OP说*排序列表* ...在这种情况下，您必须从a遍历到b。这是（结果 - [a，b]中元素的数量），所以你的总数是log n + log n +（结果 - [a，b]中元素的数量） – thang

由于列表进行排序，你可以找到一个值的位置（或者，如果该值不在列表中，它应该被插入）在O（日志（n））的时间。您只需在两端执行此操作，然后减去以获取范围内元素的数量。元素是否是整数都没有区别;该列表只需要进行排序。

你确实需要小心，如果该元素是不是唯一的;在这种情况下，在找到命中后，您可能需要对重复元素序列的末尾进行线性扫描。

来源

2013-02-07 06:41:16

lower_bound和upper_bound上有序容器操作。

首先找到该范围中的较低的值，然后从那里搜索到最后的上限值。函数的实现可能使用二进制搜索：

#include <algorithm> 
#include <list> 
#include <iterator> 

int main() { 
    using std::list; 
    using std::upper_bound; 
    using std::lower_bound; 
    using std::distance; 

    list<int> numbers = {1, 3, 5, 6, 9}; 
    int a = 3; 
    int b = 6; 

    auto lower = lower_bound(numbers.begin(), numbers.end(), 
          a); 
    auto upper = upper_bound(lower, numbers.end(), 
          b); 

    int count = distance(lower, upper); 

    return 0; 
}

来源

2013-02-07 08:14:56

什么是查找排序范围内元素数量的最快方法？

回答

相关问题