使用Python查找列表中的唯一最大值

Question

我有一组点，如下所示：

points=[ [x0,y0,v0],  [x1,y1,v1],  [x2,y2,v2].......... [xn,yn,vn]]

这些点中有些的 x 和 y 值是重复的。我想要做的是提取出唯一的最大值 x 和 y 的点。

举个例子，如果我有这些点 [1,2,5] [1,1,3] [1,2,7] [1,7,3]，

我想得到的结果是 [1,1,3] [1,2,7] [1,7,3]。

我该如何在 Python 中实现这个呢？

谢谢！

Answer 1

你可以用 dict 来实现这个功能。它有一个特点，就是“如果一个键出现多次，最后一次的值会被保留在新的字典里。”这段代码会先对点进行排序，确保最高的值在后面，然后创建一个字典，字典的键是前两个值组成的元组，值是第三个坐标，最后再把这个字典转换回一个列表。

points = [[1,2,5], [1,1,3], [1,2,7], [1,7,3]]
sp = sorted(points)
d = dict( ( (a,b), c) for (a,b,c) in sp)
results = [list(k) + [v] for (k,v) in d.iteritems()]

可能还有其他方法可以进一步优化，但这个方法已经满足你所有的要求了。

Answer 2

如果我理解你的问题的话……可以考虑用一个字典来把 (x,y) 关联到最大的 z 值。

可以这样做（这个代码没有测试过）：

dict = {}
for x,y,z in list
    if dict.has_key((x,y)):
        dict[(x,y)] = max(dict[(x,y)], z)
    else:
        dict[(x,y)] = z

不过这样做的话，顺序可能会丢失。

Answer 3

举个例子：

import itertools

def getxy(point): return point[:2]

sortedpoints = sorted(points, key=getxy)

results = []

for xy, g in itertools.groupby(sortedpoints, key=getxy):
  results.append(max(g, key=operator.itemgetter(2)))

也就是说：先把点按照xy坐标排序和分组，对于每一组固定的xy坐标，选出z值最大的那个点。如果你对itertools这个模块熟悉的话，这个看起来很简单（你应该熟悉它，因为它真的是一个非常强大和有用的模块！）。

另外，你也可以建立一个字典，用的元组作为键，z值的列表作为值，然后再最后遍历一次这个字典，找出每个对应的最大z值。不过我觉得排序和分组的方法更好（除非你有很多百万个点，这样排序的性能可能会让你担心扩展性的问题，我想）。