Для заданной строки найдите в ней первый неповторяющийся символ, выполнив только один ее обход.
Например,
Input:
string is ABCDBAGHC
Output:
первый неповторяющийся символ: D
Простым решением было бы сохранить количество каждого символа в словаре или списке, пройдя его один раз.
Затем еще раз просмотреть строку, чтобы найти первый символ, имеющий значение 1. Временная сложность этого решения равна O(n), где n длина входной строки. Проблема с этим решением заключается в том, что строка проходится дважды, что нарушает ограничения программы.
Мы можем решить эту задачу за один обход строки. Идея состоит в том, чтобы использовать словарь для хранения количества каждого отдельного символа и индекса его первого или последнего вхождения в строку. Затем пройтись по словарю и найти символ с минимальным индексом строки.
# Функция поиска первого неповторяющегося символа в
# строке, выполнив только один ее обход
def findNonRepeatingChar(s):
# Базовый вариант
if not s:
return -1
# словарь # для хранения количества символов и индекса их
# последнее вхождение в строку
d = {}
for index, char in enumerate(s):
frequency, prevIndex = d.get(char, (0, index))
d[char] = (frequency + 1, index)
# хранит индекс первого неповторяющегося символа
min_index = -1
# Проходим словарь и находим символ
for key, values in d.items():
count, firstIndex = values
if count == 1 and (min_index == -1 or firstIndex < min_index):
min_index = firstIndex
return min_index
if __name__ == '__main__':
s = 'ABCDBAGHC'
index = findNonRepeatingChar(s)
if index != -1:
print('первый неповторяющийся символ: ', s[index])
else:
print('Таких символов нет')👉 Пишите ваше решение в комментариях👇
@python_job_interview