从列表中获取每个键的最大值元组

Question

我有一个像这样的元组列表:

[(1, 0), (2, 1), (3, 1), (6, 2), (3, 2), (2, 3)]

我想保留每个元组中，第二个值相同的元组中具有最大第一个值的元组。例如，(2, 1)和(3, 1)共享相同的第二个(键)值，因此我只想保留具有最大第一个值的那个 - > (3, 1)。最终，我将得到这个:

[(1, 0), (3, 1), (6, 2), (2, 3)]

我不介意这不是一行代码，但我想知道一个有效的方法来做到这一点...

- vascop

---

我无法理解你的问题... 最大值是什么？ - TorelTwiddler

我尝试讲得清楚，但不确定是否成功。 - vascop

Answer 1

from operator import itemgetter
from itertools import groupby

[max(items) for key, items in groupby(L,key = itemgetter(1))]

假定您最初的元组列表是按关键值排序的。

“groupby”创建一个迭代器，生成类似于“(0, )” 的对象，其中第一个值是键值，第二个值是另一个迭代器，它可提供具有该键的所有元组。

“max(items)”只是选择具有最大值的元组，并且由于组中的所有第二个值相同（也是关键字），因此它给出了具有最大第一个值的元组。

使用列表推导式根据这些函数的输出形成一个输出元组列表。

- ovgolovin

---

如果它不是这样的话，你可以这样做：L.sort(key=itemgetter(1))。当然，我们不知道原帖作者是否想要稳定性... - Zach Snow

@agf 感谢您对我的英语进行纠正。我肯定应该更加小心地选择用词（例如，“过滤掉”对我来说太大胆了，最终证明并不等同于“选择”）。 - ovgolovin

经过一些测试，我发现这段代码并不完全正确：最后一个元组未被计入。如果将 [(1, 0), (2, 1), (3, 1), (6, 2), (3, 2), (2, 3)] 替换为 [(1, 0), (2, 1), (3, 1), (6, 2), (3, 2), (2, 3), (2,0)]，输出将变为 [(1, 0), (3, 1), (6, 2), (2, 3), (2, 0)]，而非我们期望的 [(1, 0), (3, 1), (6, 2), (2, 3)]。 - Rivers

@Rivers 现在明白了。这个解决方案只适用于原始列表按元组键排序的情况。我在代码后面提到了这一点。对于未排序的序列，请参考 KQ 的答案。 - ovgolovin

@ovgolovin 你说得对！我漏掉了这一部分。元组列表必须在之前按键排序。key是传递给groupby的参数，在这种情况下，它是元组的每个第二个元素（索引为1）。感谢您的阐述！ - Rivers

Answer 2

可能会使用字典：

rd = {}
for V,K in my_tuples:
  if V > rd.setdefault(K,V):
    rd[K] = V
result = [ (V,K) for K,V in rd.items() ]

- KQ.

---

我认为如果初始列表未排序，则此方法更有效，因为它只需要通过初始列表的元组进行一次传递，因此具有O(n)复杂度。而使用groupby迭代器需要对未排序的列表进行初始排序，因此具有O(n*log(n))复杂度。 - ovgolovin

这个答案也很好，因为它可以在元组列表未排序的情况下工作（在这种情况下，按元组的第二个元素排序），正如ovgolovin所提到的。 - Rivers

Answer 3

import itertools
import operator
l = [(1, 0), (2, 1), (3, 1), (6, 2), (3, 2), (2, 3)]
result = list(max(v, key=operator.itemgetter(0)) for k, v in itertools.groupby(l, operator.itemgetter(1)))

- Debilski

Answer 4

你可以使用以元组第二个元素为键的字典：

l = [(1, 0), (2, 1), (3, 1), (6, 2), (3, 2), (2, 3)]
d = dict([(t[1], None) for t in l])
for v, k in l:
  if d[k] < v:
    d[k] = v 
l2 = [ (v, k) for (k, v) in d.items() if v != None ]
print l2

- James Felix Black

---

使用基于itertools的解决方案a)可能更快，b)更加优雅。请使用其中之一。 - James Felix Black