14

我正在尝试与获取与字典中的最小值相对应的键相同 的操作，我们希望在其中获取与字典中的最小值相对应的键。

最好的方法似乎是：

min(d, key=d.get)

但我想将此应用于具有多个最小值的字典：

d = {'a' : 1, 'b' : 2, 'c' : 1}

请注意，上面的答案是：

>>> min(d, key=d.get)
'a'

但是，我需要两个具有最小值的键，即a和c。

最好的方法是什么？

（最终我想随机选择两者之一，但我认为这无关紧要）。

4

9 回答 9

14

一个简单的选择是首先确定最小值，然后选择映射到该最小值的所有键：

min_value = min(d.itervalues())
min_keys = [k for k in d if d[k] == min_value]

对于 Python 3，使用d.values()而不是d.itervalues().

这需要通过字典两次，但无论如何应该是最快的选择之一。

使用水库采样，您可以实现随机选择其中一项的单通道方法：

it = d.iteritems()
min_key, min_value = next(it)
num_mins = 1
for k, v in it:
    if v < min_value:
        num_mins = 1
        min_key, min_value = k, v
    elif v == min_value:
        num_mins += 1
        if random.randrange(num_mins) == 0:
            min_key = k

写下这段代码后，我认为这个选项具有相当的理论意义...... :)

于 2012-03-30T14:33:50.343 回答
2

已编辑：现在按照建议使用 setdefault :)

我不知道这是否对您有帮助，但您可以构建一个反向字典，其中值作为键和键（在列表中作为值）。

d = {'a' : 1, 'b' : 2, 'c' : 1}
d2 = {}
for k, v in d.iteritems():
    d2.setdefault(v, []).append(k)
print d2[min(d2)]

它会打印这个：

['a', 'c']

但是，我认为其他解决方案更紧凑，可能更优雅......

于 2012-03-30T14:39:55.703 回答
1 
min_keys = [k for k in d if all(d[m] >= d[k] for m in d)]

或者，稍微优化

min_keys = [k for k, x in d.items() if not any(y < x for y in d.values())]

它不如其他解决方案高效，但展示了 python 的美丽（至少对我而言）。

于 2012-03-30T14:46:08.740 回答
0

这有效：

d = {'a' :1, 'b' : 2, 'c' : 1}
min_value = min(d.values())
result = [x[0] for x in d.items() if x[1] == k]

嗯。在修复代码以使其正常工作后，我最终得到了@Sven Marnach 的答案，所以，忽略这个；）

于 2012-03-30T14:36:53.333 回答
0 
minValue,minKey = min((v,k) for k,v in d.items())

由于您的语义，您需要至少浏览整个字典一次。这将准确检索 1 个最小元素。

如果您想要 O(log(N)) 查询时间内的所有最小项目，您可以在生成元素时将元素插入优先级队列（如果可以的话）。优先级队列必须有 O(1) 插入时间和 O(log(N)) 提取分钟时间。（如果所有元素都具有相同的值，这将与排序一样糟糕，但否则可能会很好地工作。）

于 2012-03-30T14:37:48.897 回答
0 
def get_rand_min(d):
    min_val = min(d.values())
    min_keys = filter(lambda k: d[k] == min_val, d)
    return random.choice(min_keys)
于 2012-03-30T14:35:49.050 回答
0

您可以使用 heapq.nsmallest 来获取字典的 N 个最小成员，然后过滤掉所有不等于最小的成员。前提是您知道可以拥有的最小成员的最大数量，假设这里是 N。就像是：

from heapq import nsmallest
from operator import itemgetter

#get the N smallest members
smallestN = nsmallest(N, myDict.iteritems(), itemgetter(1)))

#leave in only the ones with a score equal to the smallest one
smallest = [x for x in smallestN if x[1] == smallestN[0][1]]
于 2012-03-30T14:35:57.643 回答
0

这是一次完成的另一种方法：

d = {'foo': 2, 'a' : 1, 'b' : 2, 'c' : 1, 'z': 99, 'x': 1}
current_min = d[d.keys()[0]]
min_keys = []
for k, v in d.iteritems():
    if v < current_min:
        current_min = v
        min_keys = [k]
    elif v == current_min:
        min_keys.append(k)
print min_keys
['a', 'x', 'c']
于 2012-03-30T14:56:25.863 回答
0

一通解决方案是：

 >>> result = [100000, []]
>>> for key, val in d.items():
...  if val < result[0]:
...   result[1] = [key]; result[0]=val;
...  elif val == result[0]:
...   result[1].append(key)
... 
>>> result
[1, ['a', 'c']]
于 2012-03-30T14:56:45.507 回答