Как создать словарь из списка без повторяющихся элементов

Question

Мне нужно создать словарь элементов без элементов, который отображается более одного раза, и я хочу сохранить начальный индекс. Пример:

a = ['a', 'b' 'a', 'c']

expected = {'b': 1, 'c': 3}

Чтобы решить проблему, я попробовал так:

def unique_array(foo):
   correct, duplicates = {}, set()
   for value in foo:
       if index, value not in enumerate(correct):
          correct[value] = index
       else:
          duplicates.add(value)
   return {k: correct[k] for k in set(correct) - duplicates

Есть лучший и более эффективный способ сделать это?

Answer 1

Одним из решений является использование Counter и двух проходов. (Это все еще O (n).)

>>> from collections import Counter 
>>> a = ['a', 'b', 'a', 'c']                                                    
>>> counts = Counter(a)                                                         
>>> {k:idx for idx, k in enumerate(a) if counts[k] == 1}                        
{'b': 1, 'c': 3}

Answer 2

У вас есть два встроенных цикла, что усложняет временную сложность вашего кода O (n ^ 2).

Решение O (n) может быть:

a = ['a', 'b', 'a', 'c']

out = {}
for index, val in enumerate(a):
    if val not in out:
        out[val] = index
    else:
        out[val] = None

out = {item:val for item, val in out.items() if val is not None}



print(out)
# {'b': 1, 'c': 3}

Сначала мысоздайте вывод, помечая дубликаты значением None, когда мы их встречаем. В конце мы отфильтровываем ключи со значением None. Обе операции O (n).

Answer 3

Вы можете сделать это, используя один цикл

alphabets = ['a', 'b', 'a', 'c']
alphabetDict = {}
index = 0
for alphabet in alphabets:
    count = alphabets.count(alphabet)
    if count == 1:
        alphabetDict[alphabet] = index
        index += 1
    else:
        index += 1
        continue

print(alphabetDict)