Понимание, чтобы найти мин в диктовке

Question

Мне любопытно кое-что:

У меня есть диктат, например, с ключом автомобиля и значением относительно его скорости.Теперь я хочу найти ключ с наименьшим значением.

car_dict = {'mercedes': 200, 'fiat': 100, 'porsche': 300, 'rocketcar': 600}

Я знаю, что этот код работает с O (1)

car_value = list(car_dict.values())
car_key = list(car_dict.keys())
min_stats = min(car_value)
print(car_key[car_value.index(min_stats)]) 

, и этот тоже с O (n)

keys = []
values = []
for name, value in car_dict.items():
    keys.append(name)
    values.append(value)

min_value = min(values)
print(keys[values.index(min_value)])

В настоящее время я пытаюсь лучше понять понимание, поэтому мой вопрос заключается в том, возможен ли подход к этой проблеме с использованием списочных пониманий.

Я думал о чем-то подобном

worst = {name for name, stats in car_dict if min(stats)}

Тем не менее, я думаю, что я все еще неправильно что-то понимаю в части if.

Кстати, поправьте меня, если я ошибаюсь из-за своей веры в сложность Большого О, описанную выше.

Большое спасибо!

Answer 1

Дело в том, что вы не должны решать эту проблему с пониманием, потому что вы не можете выполнять задания в понимании.Итерируя словарь, вы можете найти минимум за один проход:

car_iterator = iter(car_dict.items())
slowest_car, min_speed = next(car_list)
for car, speed in car_iterator:
    if speed < min_speed:
        slowest_car = car

Answer 2

Как насчет этого:

car_dict = {'mercedes': 200, 'fiat': 100, 'porsche': 300, 'rocketcar': 600}
min_car = {}
for car in car_dict:
    if not min_car or car_dict[car] < min_car['speed']:
        min_car['name'] = car
        min_car['speed'] = car_dict[car]
print(min_car)

Answer 3

хорошо, я не уверен, каково время выполнения этого, но вы можете попробовать это, оно работает для меня:

>>> d = {'mercedes': 200, 'fiat': 100, 'porsche': 300, 'rocketcar': 600}
>>> d.items()
[('mercedes', 200), ('fiat', 100), ('porsche', 300) , ('rocketcar',600)]
>>> # find the minimum by comparing the second element of each tuple
>>> min(d.items(), key=lambda x: x[1]) 
('fiat', 100)

Answer 4

Вы не можете решить эту проблему быстрее линейного времени, но вы можете решить ее за линейное время за один проход :

min_speed = None
that_car = None
for car,speed in car_dict.items():
    if min_speed is None or speed < min_speed:
        that_car, min_speed = car, speed
that_car
#'fiat'

Answer 5

Я знаю, что этот код работает с O (1):

car_value = list(car_dict.values())

Это неверно.Чтобы сформировать список из представления, вы должны перебрать все значения.Эта операция будет иметь временную сложность O (n).

В общем случае создание списка ключей и значений не требуется.Избегайте этих операций, так как они дорогостоящие.

Обратите внимание, что min может работать непосредственно с dict.items, который представляет собой пару пар ключ-значение.Это только рекомендуется, если у вас есть только один автомобиль с минимальным значением:

car, value = min(car_dict.items(), key=lambda x: x[1])  # (fiat, 100)

Поскольку словари не считаются упорядоченными (если вы не используете Python 3.7), для дублирующих минимумов результат не будет определенным.В этом случае вы можете вычислить минимальное значение и затем использовать понимание списка:

min_val = min(car_dict.values())
min_cars = [car for car, value in car_dict.items() if value == min_val]  # ['fiat']

Вы также можете использовать next с выражением генератора для извлечения первого такого автомобиля:

min_car_first = next(car for car, value in car_dict.items() if value == min_val)

Конечно, в случае одного автомобиля с минимальным значением это даст тот же результат, что и первое решение min(car_dict.items(), ...).

Answer 6

Это позволит вам сравнить значение ключа с минимумом значений

worst = [i for i in car_dict if car_dict[i] == min(car_dict.values())]