поиск ключа в словаре с n-м наибольшим значением

#python #algorithm #dictionary

#python #алгоритм #словарь

Вопрос:

учитывая словарь, подобный этому: example_dict ={"mark":13, "steve":3, "bill":6, "linus":11}

легко найти ключ с максимальным значением max(example_dict.items(), key=operator.itemgetter(1)) и минимальным значением min(example_dict.items(), key=operator.itemgetter(1))

Какой самый простой способ найти ключ с n-м наибольшим значением? например, ключ со 2-м по величине значением здесь linus

1. Составьте список всех значений и найдите 3-е по величине. Затем найдите в словаре все ключи с этим значением.

2. Я полагаю, что сортировка будет самым быстрым способом. По крайней мере, не найдя max, удалите его и выполните поиск снова. Поэтому я бы выбрал первое, сортировку и поиск

3. Обратите внимание, что ваши коды для min и max не работают, если есть повторяющиеся значения. Они просто вернут один из дубликатов, а не все из них.

4. @ErikvandeVen: нет. Известно, что задача выбора n-го наибольшего элемента «проще», чем сортировка, и известен алгоритм O (N) наихудшего времени.

5. @YvesDaoust но просто из любопытства: это учитывается только в том случае, если есть только один n-й элемент, который вы хотите извлечь, верно? И вы имеете в виду quickselect?

Ответ №1:

Используйте nlargest:

 import heapq

example_dict ={"mark":13, "steve":3, "bill":6, "linus":11}

*_, res = heapq.nlargest(2, example_dict, key=example_dict.get)
print(res)

Вывод

 linus

Из документации:

Возвращает список с n наибольшими элементами из набора данных, определенного с помощью iterable . ключ, если он указан, задает функцию с одним аргументом, которая используется для извлечения ключа сравнения из каждого элемента в iterable (например, key=str.lower).

Примечание о производительности, также из документации:

лучше всего работает при меньших значениях n. Для больших значений более эффективно использовать функцию sorted() . Кроме того, когда n == 1, более эффективно использовать встроенные функции min() и max() . Если требуется повторное использование этих функций, рассмотрите возможность превращения итерации в фактическую кучу.

Обратите внимание, что он возвращает список, поэтому вы отбрасываете первые n-1 элементы

Ответ №2:

Используйте алгоритм быстрого выбора. Он работает в O (n) в среднем

Ответ №3:

Что-то вроде этого:

 def nth_largest_key(di, n):
    sorted_items = sorted(di.items(), key=lambda item: item[1],
                          reverse=True)
    return sorted_items[n-1][0]


input_di = {"mark":13, "steve":3, "bill":6, "linus":11}
print(nth_largest_key(input_di, int(input().strip())))