如何在嵌套列表中根据其内部列表的第一个元素获取所有最小元素？

Question

简单来说，有这样一个列表 LST = [[12,1],[23,2],[16,3],[12,4],[14,5]]，我想根据内部列表的第一个元素获取这个列表中所有最小的元素。所以对于上面的例子，答案将是[12,1]和[12,4]。在Python中有没有一种典型的方法可以做到这一点？提前感谢您。

- consumer

---

这是一个常见的问题，请搜索。http://stackoverflow.com/questions/3259159/sorting-a-list-of-tuples - S.Lott

@SLott：你链接的问题与原帖的问题完全不同。 - kennytm

@KennyTM：怎么会呢？它们在我看来完全一样啊。我错过了什么区别吗？ - S.Lott

@SLott：感谢您指出链接。不幸的是，我看到那个链接与此无关。 - consumer

Answer 1

两次遍历：

minval = min(LST)[0]
return [x for x in LST if x[0] == minval]

一次遍历：

def all_minima(iterable, key=None):
  if key is None: key = id
  hasminvalue = False
  minvalue = None
  minlist = []
  for entry in iterable:
     value = key(entry)
     if not hasminvalue or value < minvalue:
        minvalue = value
        hasminvalue = True
        minlist = [entry]
     elif value == minvalue:
        minlist.append(entry)
  return minlist

from operator import itemgetter
return all_minima(LST, key=itemgetter(0))

- kennytm

Answer 2

一个紧凑的单遍解决方案需要对列表进行排序——对于长度为N的列表，这在技术上是O(N log N)，但Python的排序非常好，并且许多序列“恰好”在其中嵌入了一些顺序（timsort巧妙地利用这些顺序以加快速度），因此基于排序的解决方案有时在实际中表现出惊人的性能。

以下是需要2.6或更高版本的解决方案：

import itertools
import operator
f = operator.itemgetter(0)

def minima(lol):
  return list(next(itertools.groupby(sorted(lol, key=f), key=f))[1])

为了理解这种方法，从“内部向外”看会有所帮助。 f，即operator.itemgetter(0)，是一个关键函数，用于选择其参数的第一个项目进行排序 - operator.itemgetter的目的就是轻松而简洁地构建这样的函数。

因此，sorted(lol，key=f)返回按递增顺序排列的列表lol的排序副本。如果省略key=f，则排序后的副本将按字典顺序排序，因此它也将按第一项递增的顺序排序，但仅作为“主键” - 具有相同第一子项的项将依次按第二个子项的值进行排序，等等 - 而使用key=f，您可以保留具有相同第一子项的项目之间的原始顺序。您没有指定需要哪种行为（在您的示例中，两种行为恰好产生相同的结果，因此我们无法从该示例中区分），这就是我仔细详细说明两种可能性的原因，以便您可以选择。 itertools.groupby(sorted(lol，key=f)，key=f)执行“分组”任务，这是操作的核心：它根据key排序标准从序列（在本例中为sorted提供的序列）中产生组。也就是说，一个组与所有相邻项一起产生相同的值，当您使用该项作为参数调用f时，然后是一个组，其所有相邻项从第一组产生不同的值（但在他们之间相同），等等。 groupby尊重其参数的排序顺序，这就是为什么我们必须首先对lol进行排序的原因（groupby的这种行为使其在许多情况下非常有用，其中序列的排序确实很重要）。

由groupby yield的每个结果都是一对k，g：一个键k，它是在组中的每个项目上使用f（i）的结果，一个迭代器g，它按顺序生成组中的每个项目。 next内置函数（此解决方案中唯一需要Python 2.6的部分）给定一个迭代器生成其下一个项 - 特别是在新制作的迭代器上调用时的第一项（当然，每个生成器都是一个迭代器，就像groupby的结果一样）。在早期的Python版本中，它必须是groupby（...）。next（）（因为next仅是迭代器的方法，而不是内置函数），自2.6以来已弃用。

因此，总结一下，我们的next(...)的结果正是一对k,g，其中k是第一个子项中最小（即排序后的第一个）值，g是该组项目的迭代器。

因此，通过使用[1]，我们只选择迭代器，这样我们就有了一个只产生我们想要的子项的迭代器。

由于我们想要一个列表而不是迭代器（根据您的规格），所以最外层的list(...)调用完成了工作。

从性能的角度来看，所有这些是否值得？在您提供的微小示例列表上并非如此 - minima实际上比@Kenny答案中的任何代码都要慢（其中第一个“两遍”解决方案更快）。 我只是认为值得记住这些想法，以解决您可能遇到的next序列处理问题，其中典型输入的细节可能会非常不同（更长的列表，较少的最小值，输入中的部分排序等等）。

- Alex Martelli

Answer 3

m = min(LST, key=operator.itemgetter(0))[0]
print [x for x in LST if x[0] == m]

- Ignacio Vazquez-Abrams

Answer 4

minval = min(x[0] for x in LST)
result = [x for x in LST if x[0]==minval]

- interjay