如何对一个列表的列表进行排序并仅保留每个第一元素的最大第二元素？

Question

假设我有一个列表：

lst = [[2,6],[1,4],[0,1],[1,1],[2,3],[0,2]]

我想按照第一个元素将 lst 排序，并在按第一个元素分组时保留具有最大第二个元素的子列表。 因此结果将是：

results
>>> [[0,2],[1,4],[2,6]]

有人可以帮我一下吗？

- Guy

Answer 1

你可以使用 np.maximum.reduceat 来实现：

import numpy as np
lst = np.array([[2,6],[1,4],[0,1],[1,1],[2,3],[0,2]])
lst = lst[np.argsort(lst[:,0])] #sorting lst by first row
u, idx = np.unique(lst[:,0], return_index = True) 
print(np.c_[u, np.maximum.reduceat(lst[:,1], idx)])

首先需要对数组进行排序。然后需要获取将数组分成组的索引：idx = [0, 2, 4]和第一列相应的值u = [0, 1, 2]。最后，使用np.maximum.reduceat来获取指定索引idx开始的组的最大值，并将其连接到u的右侧显示。

备注：这里使用了广泛使用的库numpy，该库允许将循环推入C级别，从而实现更快的速度。纯python解决方案也值得关注。

奖励：这实际上是一个单行代码，使用专门用于数组分组操作的numpy_indexed库（不太常用）。

import numpy_indexed as npi
import numpy as np
np.transpose(npi.group_by(lst[:, 0]).max(lst[:, 1]))

- mathfux

Answer 2

假设你只有这样的“配对”（例如，每个子列表始终有两个整数，第一个值相同，第二个值不同），那么非常简单：

>>> lst = [[2,6],[1,4],[0,1],[1,1],[2,3],[0,2]]
>>> sorted(lst)[1::2]
[[0, 2], [1, 4], [2, 6]]

默认情况下，通过对每个子列表的第1个和第2个值进行排序来对列表进行排序，然后只需切片结果列表以获取每隔一个项目

- Chris_Rands

---

在切片时，您还假设每个不同的第一个值恰好有两个子列表，但您没有说明这种假设。 - Stef

@Stef 是的，完全正确，这也是我所说的“对”所指的，但我没有解释清楚。 - Chris_Rands

@Chris_Rands，它的措辞有点奇怪，但我明白你的意思。我认为这是一个合理的假设（这就是为什么我给了第一个赞），因为如果不是这种情况，示例数据将会很糟糕，并且有一些应用程序会这样做，例如存储 (object_id, x_coordinate) 对的算法。对于每个对象，会有一对坐标，一对是“进入”对象（包括其左坐标），另一对是“离开”对象（包括其右坐标）。虽然如此，就像我的答案中所述，应用 dict 不需要太多的工作量，并使其更加通用 :-) - superb rain

Answer 3

将列表排序，按第一个元素分组，然后在每个组中保留第二个元素的最大值

import itertools as it
from operator import itemgetter

lst = [[2,6],[1,4],[0,1],[1,1],[2,3],[0,2]]

slst = sorted(lst, key=itemgetter(0))
gs = it.groupby(slst, key=itemgetter(0))
res = [max(v, key=itemgetter(1)) for k,v in gs]
print(res)

生成

[[0, 2], [1, 4], [2, 6]]

- Pynchia

---

如果我的解决方案不基于numpy，我会使用itertools.groupby。这与numpy.unique类似。 - mathfux

没问题。很高兴能帮助他人提供一个通用列表。 - Pynchia

Answer 4

尝试使用以下代码段，无需任何imports。

lst = [[2,6],[1,4],[0,1],[1,1],[2,3],[0,2]]

lst = sorted(lst) # Sort the list in increasing order.
lst = [lst[i] for i in range(len(lst)) if i+1 == len(lst) or lst[i+1][0] != lst[i][0]]
# Remove the elements with minimum 2nd element.

print(lst)

输出：

[[0, 2], [1, 4], [2, 6]]

- solid.py

Answer 5

另一种方式是使用一个 dict。

>>> [*dict(sorted(lst)).items()]
[(0, 2), (1, 4), (2, 6)]

它生成的是元组而不是列表，但你甚至接受了一个生成numpy数组的答案。要获取列表：

>>> [*map(list, dict(sorted(lst)).items())]
[[0, 2], [1, 4], [2, 6]]

这些解决方案有效是因为dict会为每个键保留最后的值，因此如果我们先排序，那么最后的值就是最大的。

- superb rain

---

不错的方法！假设使用CPython 3.6+，其中字典保留插入顺序。 - Chris_Rands

@Chris_Rands 嗯。我很久以前就从假定CPython 3.6+转到假定Python 3.7+。已经过去两年了:-)。但我刚刚检查了一下，这五个替代实现中只有一个是3.7+的。因此，假设Python 3.7+不会扩大用户集，而是缩小用户集。无论如何，对于非有序字典，sorted(dict(sorted(lst)).items())。 - superb rain