我需要在不断变化的大型集中找到最小值/最大值，在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] 删除。
我来说两句