根据内部列表元素的比较从列表列表中移除重复项

Question

需要根据特定条件删除大量元素：

1. 唯一性由列表的第一个元素决定。在
2. 重复项的删除是通过比较重复列表的第二个元素的值来确定的，即保留具有最低第二个元素的列表。在

[[1, 4, 5], [1, 3, 4], [1, 2, 3]]

以上所有列表都被认为是重复的，因为它们的第一个元素是相等的。第三个列表需要保留，因为它的第二个元素是最小的。注意，实际的列表列表有超过400万个元素，是双重排序的，需要保留排序。在

首先根据内部列表的第二个元素对列表进行排序，并按倒序（降序）排序，然后根据第一个元素按正常（升序）顺序排序：

sorted(sorted(the_list, key=itemgetter(1), reverse=True), key=itemgetter(0))

三个实际排序的重复列表示例：

^{pr2}$

目标是准备列表以进行对分搜索。有人能告诉我如何使用Python实现这一点吗？在

Answer 1

可以使用dict对元素进行分组，始终使用较小的第二个元素保留子列表：

l = [[1, 2, 3], [1, 3, 4], [1, 4, 5], [2, 4, 3], [2, 5, 6], [2, 1, 3]]
d = {}
for sub in l:
    k = sub[0]
    if k not in d or sub[1] < d[k][1]:
        d[k] = sub

也可以将两个键传递给sorted，不需要调用sorted两次：

^{pr2}$

如果您想按照维护dict中的顺序，则需要保留顺序。：

^{3}$

但不确定这是否合适，因为你在排序之后的数据，所以你会失去任何顺序。在

您可能会发现非常有用的是sortedcontainers.sorteddict：

A SortedDict provides the same methods as a dict. Additionally, a SortedDict efficiently maintains its keys in sorted order. Consequently, the keys method will return the keys in sorted order, the popitem method will remove the item with the highest key, etc.

An optional key argument defines a callable that, like the key argument to Python’s sorted function, extracts a comparison key from each dict key. If no function is specified, the default compares the dict keys directly. The key argument must be provided as a positional argument and must come before all other arguments.

from sortedcontainers import SortedDict

l = [[1, 2, 3], [1, 3, 4], [1, 4, 5], [2, 4, 3], [2, 5, 6], [2, 1, 3]]
d = SortedDict()
for sub in l:
    k = sub[0]
    if k not in d or sub[1] < d[k][1]:
        d[k] = sub


print(list(d.values()))

它有您想要的所有方法bisect，bisect_left等。。在

Answer 2

如果我没弄错，解决方法可能是这样的：

mylist = [[1, 2, 3], [1, 3, 4], [1, 4, 5], [7, 3, 6], [7, 1, 8]]

ordering = []
newdata = {}

for a, b, c in mylist:
    if a in newdata:
        if b < newdata[a][1]:
            newdata[a] = [a, b, c]
    else:
        newdata[a] = [a, b, c]
        ordering.append(a)

newlist = [newdata[v] for v in ordering]

所以在newlist中，我们将收到[[1, 2, 3], [7, 1, 8]]的简化列表。在