在python中查找变化集的最小值和最大值的有效方法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了在python中查找变化集的最小值和最大值的有效方法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1253字，纯文字阅读大概需要2分钟。

内容图文

我需要在不断变化的大型集中找到最小/最大值,在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集(使用哈希表)并在对象中保留一对maxElement和minElement属性,并在添加或删除元素时相应地更新它们.这样可以保留每个存在性的查询,即最小和最大O(1).但是,对于最简单的实现,删除操作将是O(n)最坏的情况(因为如果您碰巧删除了最小元素,则必须找到倒数第二个元素,而对于最大元素,删除操作也是如此).

也就是说,C实现使用平衡的搜索树,该树具有O(log n)存在检查,删除和插入操作.您可以在bintrees软件包中找到这种数据结构的实现.

我不会像注释中所建议的那样仅使用heapq,因为堆是O(n)来检查元素的存在(我猜想您需要的是设置数据结构的要点).

内容总结

以上是互联网集市为您收集整理的在python中查找变化集的最小值和最大值的有效方法全部内容，希望文章能够帮你解决在python中查找变化集的最小值和最大值的有效方法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端