python - 优化用于更改列表的最小函数

Question

我正在处理一个问题，我需要跟踪列表中的最小数字。然而，这个列表在不断减少，比如从一百万个元素到一个元素。我一直在寻找一种方法来避免每次我得到一个较小的元素列表时都检查最小值。就像跟踪最小元素一样，如果它被删除，下一个最小值将成为最小值。我想在线性时间内完成这个。(考虑到问题的机制，它应该是可以实现的)

我从一开始就想到，我可以使用 collections Counter 来对列表中的元素进行计数。然后我找到最小值(已经是 O(2*n))，并且每次删除一个元素时，我都会从字典键的值中减去 1。然而，当最小数的计数用完时，我仍然需要找到第二个最小元素，以便它可以替换它。

请帮我找到解决办法。我会说这是一个有趣的问题。

Answer 1

假设您的程序需要一些时间来对该列表进行排序

a = [10,9,10,8,7,6,5,4,3,2,1,1,1,0] # you're just removing 
a = sorted(a) #sort ascending

# then you remove stuff from your list
# but always a[0] is minimum element

min = a[0] #you must be careful, there must be at least one item so check that before 
#getting the min

这样就不用每次都找了