我需要在std :: set中找到元素的索引.此索引可以显示为迭代器从头开始的距离.一种方法是:
for(int i = 0, set<int>::iterator it = s.begin(); it != iteratorToBeFound; ++it, ++i);
这显然需要O(n)时间.但我们知道,在内部使用set实现的二叉搜索树中根的距离可以在O(log n)时间内找到.
他们以任何方式实现相同的功能,在C++中设置O(log n)时间的索引吗？
我有一个整数序列{a1,a2 ... an},我想把它分成最小数量的"递增子序列".例如:让序列为{10,30,20,40},然后答案为2.在这种情况下,第一个增加序列为{10,30,40},第二个增加序列为{20}.我能够使用O(N ^ 2)算法来做到这一点但我对O(N*logN)解决方案特别感兴趣,它可以达到目的.