Компактное однопроходное решение требует сортировки списка - это технически O(N log N) для 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) выполняет задачу «группировки», которая является ядром операции: он выдает групп из последовательности (в данном случае последовательность sorted обеспечивает) на основе keyкритерии заказа.То есть группа со всеми смежными элементами выдает одинаковое значение между собой, когда вы вызываете f с элементом в качестве аргумента, затем группа со всеми смежными элементами выдает значение, отличное от первой группы (но одинаковое между собой),и так далее.groupby соблюдайте порядок последовательности, принимаемой в качестве аргумента, поэтому нам пришлось сначала отсортировать lol (и такое поведение groupby делает его очень полезным во многих случаях, когда порядок последовательности имеет значение).
Каждый результат yield, отредактированный groupby, представляет собой пару 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 , с которой вы можете столкнуться, когда детали типичных входных данных могут сильно отличаться (более длинные списки, более редкие минимумы, частичное упорядочение на входе и т. Д., & c; -).