<p>下面是一个简单易懂的动态过程方法:</p>
<pre><code>class Object:
def __init__(self, somelist):
self.classification = somelist[0] # String
self.type = somelist[1] # String
self.first = somelist[2] # Integer
self.last = somelist[3] # Integer
def weight(self):
return self.last - self.first
def __str__(self):
return "Object(%r, %r, %r, %r)" % (self.classification, self.type, self.first, self.last)
__repr__ = __str__
obj1 = Object(['A', 'x', 4, 17])
obj2 = Object(['A', 'y', 5, 20])
obj3 = Object(['B', 'z', 10, 27])
obj4 = Object(['B', 'z', 2, 15])
obj5 = Object(['B', 'z', 20, 40])
obj6 = Object(['A', 'x', 6, 10])
obj7 = Object(['A', 'x', 2, 9])
olist = [obj1, obj2, obj3, obj4, obj5, obj6, obj7]
mindict = {}
for o in olist:
key = (o.classification, o.type)
if key in mindict:
if o.weight() >= mindict[key].weight():
continue
mindict[key] = o
from pprint import pprint
pprint(mindict)
</code></pre>
<p>输出如下:</p>
^{pr2}$
<p>注意:<code>__str__</code>、<code>__repr__</code>和{<cd3>}只是为了得到精美的打印输出,这不是必需的。同样,上面的代码在python2.2到2.7上运行不变。在</p>
<p><strong>运行时间</strong>:O(N),其中N是列表中的对象数。对对象进行排序的解决方案平均为O(N*log(N))。另一个解决方案是O(K*N),其中K<;=N是从对象派生的唯一(分类、类型)键的数量。在</p>
<p><strong>使用的额外内存</strong>:仅O(K)。其他的解决方案似乎是O(N)。在</p>