我在开发一个算法来确定n个元素的最小值时遇到了一些困难。不是求长度为n的数组的最小值,这很简单:
min = A[0]
for i in range(1, len(A)):
if min > A[i]: min = A[i]
print min
但我的列表包含对象:
^{pr2}$对于相同的“分类类型”对象,我有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]
所以我需要一个算法来确定列表的最小值:
一个| x-->对象(['A','x',6,10])
B | z-->;对象(['B','z',2,15])
一个| y-->对象(['A','y',5,20])
谢谢!在
下面是一个简单易懂的动态过程方法:
输出如下:
^{pr2}$注意:}只是为了得到精美的打印输出,这不是必需的。同样,上面的代码在python2.2到2.7上运行不变。在
__str__
、__repr__
和{运行时间:O(N),其中N是列表中的对象数。对对象进行排序的解决方案平均为O(N*log(N))。另一个解决方案是O(K*N),其中K<;=N是从对象派生的唯一(分类、类型)键的数量。在
使用的额外内存:仅O(K)。其他的解决方案似乎是O(N)。在
group_func
返回一个包含对象分类的元组键,然后是type(例如('A', 'x')
)。这首先用于对列表l
(sorted
调用)进行排序。然后,我们在排序后的列表上调用groupby
,使用group_func
分组到子列表中。每次密钥更改,我们都有一个新的子列表。与SQL不同,groupby要求在同一个键上对列表进行预排序。map
接受groupby
函数的输出。对于每个组,map
返回一个元组。第一个元素是pair[0]
,它是键('A', 'x')
。第二个是组(pair[1]
)的最小值,由last - first
键确定。在注意:不要将变量命名为
list
:它隐藏了内置变量。在相关问题 更多 >
编程相关推荐