确定n个元素列表的最小值

Question

我在开发一个算法，用来找出一组n个元素中的最小值时遇到了一些麻烦。找出一个长度为n的数组的最小值很简单：

min = A[0]
for i in range(1, len(A)):
    if min > A[i]: min = A[i]
print min

但我的列表里包含的是对象：

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

而且对于同一种“分类 | 类型”的对象，我有m个元素，我想通过比较第一个和最后一个元素之间的差异来找出同一“分类 | 类型”的最小元素。

举个例子：

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])
list = [obj1, obj2, obj3, obj4, obj5, obj6, obj7]

所以我需要一个算法来确定列表中的最小值：

A | x --> 对象(['A', 'x', 6, 10])

B | z --> 对象(['B', 'z', 2, 15])

A | y --> 对象(['A', 'y', 5, 20])

谢谢！

Answer 1

这里有一种简单易懂的动态过程方法：

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)

这是输出结果：

{('A', 'x'): Object('A', 'x', 6, 10),
 ('A', 'y'): Object('A', 'y', 5, 20),
 ('B', 'z'): Object('B', 'z', 2, 15)}

注意：__str__、__repr__和pprint这些东西只是为了让输出看起来更好看，并不是必须的。而且上面的代码在Python 2.2到2.7的版本中都可以正常运行。

运行时间：O(N)，其中N是列表中对象的数量。那些对对象进行排序的解决方案平均需要O(N * log(N))的时间。还有一种解决方案的时间复杂度是O(K * N)，其中K <= N是从对象中得到的唯一（分类，类型）键的数量。

额外使用的内存：只需要O(K)。其他的解决方案似乎需要O(N)的内存。

Answer 2

filtered = [obj for obj in lst if obj.classification == 'A' and obj.type = 'x']
min(filtered, key=lambda x: x.last - x.first)

注意：不要把你的变量命名为 list，因为这样会覆盖掉内置的功能。

Answer 3

import itertools 
group_func = lambda o: (o.classification, o.type)
map(lambda pair: (pair[0], min(pair[1], key=lambda o: o.last - o.first)),
    itertools.groupby(sorted(l, key=group_func), group_func))

group_func 函数会返回一个包含对象分类的元组键，比如 ('A', 'x')。这个元组首先用来对列表 l 进行排序（调用 sorted）。接着，我们在排序后的列表上调用 groupby，使用 group_func 来把数据分成小组。每当键值变化时，就会生成一个新的小组。和 SQL 不同的是，groupby 要求列表必须先按相同的键进行排序。map 函数会处理 groupby 的输出。对于每个小组，map 返回一个元组。第一个元素是 pair[0]，也就是键 ('A', 'x')。第二个元素是这个小组中的最小值（pair[1]），这个最小值是通过 last - first 键来确定的。