我需要在不断变化的大型集中找到最小值/最大值,在C ++中,可能是
#include<set>
using namespace std;
int minVal(set<int> & mySet){
return *mySet.begin();
}
int maxVal(set<int> & mySet){
return *mySet.rbegin();
}
int main(){
set <int> mySet;
for(..;..;..){
// add or delete element in mySet
...
// print the min and max value in the set
printf("%d %d\n", minVal(mySet), maxVal(mySet));
}
}
在C ++中,每个查询操作都是O(1),但是在python中,我尝试使用内置方法min和max,但这太慢了。每个最小/最大操作花费O(n)时间(n是我的Set的长度)。是否有任何优雅而有效的方法来做到这一点?还是任何数据类型支持这些操作?
mySet=set()
for i in range(..):
# add or delete element in mySet
...
# print the min and max value in the set
print(min(mySet),max(mySet))
就复杂性而言,有效的实现方式是包装一个python set
(使用哈希表)并在对象中保留一对maxElement
和minElement
属性,并在添加或删除元素时相应地更新它们。这将保留每个存在性的查询,即最小和最大O(1)。但是,对于最简单的实现,删除操作将是O(n)最坏的情况(因为如果您碰巧删除了最小元素,则必须找到倒数第二个元素,而对于最大元素,删除操作也是一样)。
也就是说,C ++实现使用平衡的搜索树,该树具有O(log n)存在检查,删除和插入操作。您可以在bintrees包中找到这种数据结构的实现。
我不会heapq
像注释中所建议的那样使用a ,因为堆是O(n)来检查元素的存在(我猜想您需要的是设置数据结构的要点)。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句