Python: поиск ключей с уникальными значениями в словаре?

Я получаю словарь в качестве входных данных и хочу вернуть список ключей, для которых значения словаря являются уникальными в объеме этого словаря.

Я поясню пример. Скажем, мой ввод – словарь a, построенный следующим образом:

a = dict() a['cat'] = 1 a['fish'] = 1 a['dog'] = 2 # <-- unique a['bat'] = 3 a['aardvark'] = 3 a['snake'] = 4 # <-- unique a['wallaby'] = 5 a['badger'] = 5 

Результат, который я ожидаю, это ['dog', 'snake'] .

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

Я думаю, что эффективный способ, если бы диктовать слишком большой, был бы

 countMap = {} for v in a.itervalues(): countMap[v] = countMap.get(v,0) + 1 uni = [ k for k, v in a.iteritems() if countMap[v] == 1] 

Вот решение, которое требует только один раз:

 def unique_values(d): seen = {} # dict (value, key) result = set() # keys with unique values for k,v in d.iteritems(): if v in seen: result.discard(seen[v]) else: seen[v] = k result.add(k) return list(result) 

Обратите внимание, что это на самом деле грубая сила:

 l = a.values() b = [x for x in a if l.count(a[x]) == 1] 
 >>> b = [] >>> import collections >>> bag = collections.defaultdict(lambda: 0) >>> for v in a.itervalues(): ... bag[v] += 1 ... >>> b = [k for (k, v) in a.iteritems() if bag[v] == 1] >>> b.sort() # optional >>> print b ['dog', 'snake'] >>> 

Немного более подробный, но ему нужен только один проход:

 revDict = {} for k, v in a.iteritems(): if v in revDict: revDict[v] = None else: revDict[v] = k [ x for x in revDict.itervalues() if x != None ] 

(Я надеюсь, что это сработает, поскольку я не могу проверить его здесь)

Как насчет подкласса?

 class UniqueValuesDict(dict): def __init__(self, *args): dict.__init__(self, *args) self._inverse = {} def __setitem__(self, key, value): if value in self.values(): if value in self._inverse: del self._inverse[value] else: self._inverse[value] = key dict.__setitem__(self, key, value) def unique_values(self): return self._inverse.values() a = UniqueValuesDict() a['cat'] = 1 a['fish'] = 1 a[None] = 1 a['duck'] = 1 a['dog'] = 2 # <-- unique a['bat'] = 3 a['aardvark'] = 3 a['snake'] = 4 # <-- unique a['wallaby'] = 5 a['badger'] = 5 assert a.unique_values() == ['dog', 'snake'] 

Вот еще один вариант.

 >>> import collections >>> inverse= collections.defaultdict(list) >>> for k,v in a.items(): ... inverse[v].append(k) ... >>> [ v[0] for v in inverse.values() if len(v) == 1 ] ['dog', 'snake'] 

Я частично отношусь к этому, потому что перевернутый словарь является таким общим шаблоном проектирования.

Вы можете сделать что-то вроде этого (просто подсчитайте количество вхождений для каждого значения):

 def unique(a): from collections import defaultdict count = defaultdict(lambda: 0) for k, v in a.iteritems(): count[v] += 1 for v, c in count.iteritems(): if c <= 1: yield v 

Использовать вложенные списки!

 print [v[0] for v in dict([(v, [k for k in a.keys() if a[k] == v]) for v in set(a.values())]).values() if len(v) == 1]