Как удалить символы, которые появляются более одного раза из строки?

Question

Итак, у меня было похожее упражнение на моих IT-классах: «Напечатать строку без символов, появляющихся более одного раза (если они появляются более одного раза, удалите их)». Я думал, что это было легко (и, возможно, так и есть), но я совершенно не представляю, как это сделать. Я могу выполнять аналогичные упражнения (распечатать все уникальные символы из строки / удалить дубликаты и т. Д. c).

Пример:

Ввод: '12345555555678'

Ввод: ' 1234678'

Answer 1

базовый c алгоритм для этого описан в этом ответе - для каждого символа, который вы проверяете, появляется ли он более одного раза, подсчитывая его вхождения в строке.

Однако это довольно неэффективно, поскольку идет через строку n ^ 2. Вы можете улучшить это, потратив немного памяти (что проиллюстрировано в этом ответе - но запутано библиотекой ).

Тогда алгоритм будет go однократно проходить через строку и подсчитывать количество вхождений для каждого символа и сохранять их где-то, затем go снова проходить через строку и печатать только те символы, у которых есть количество 1.

inp = '1345552225555678'

counts = {};

for ch in inp:
    if ch in counts:
        counts[ch] = counts[ch] + 1
    else:
        counts[ch] = 1

result = '';

for ch in inp:
    if counts[ch] == 1:
        result = result + ch

print result

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

Примечание: Обычно это делается с использованием массива размером с число допустимых символов, но поскольку строки в python являются Unicode, массив будет огромным, однако время доступа будет действительно O (1);

Answer 2

i_str =  '12345555555678'
b = sorted(i_str)
for i in range(len(b)-1):
    if b[i] == b[i+1]:
        i_str = i_str.replace(b[i],'')

Вы просто сортируете строку и сравниваете каждый n-й элемент со следующим элементом. Если это не то же самое, это уникально.

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

Answer 3

Вы можете использовать collections.Counter().

from collections import Counter

inp = '12345555555678'
c = Counter(inp)
output = ''.join(k for k, v in c.items() if v == 1)  # -> 1234678

---

Простая реализация счетчика

c = {}
for char in inp:
    c[char] = c.get(char, 0) + 1

Answer 4

Это должно выглядеть так, как вы хотите

input_str = 'ahuadvzudnioqdazvyduazdazdui'
for c in input_str:
    if input_str.count(c)==1:
        print(c)

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

Чтобы сделать его немного быстрее вы можете использовать список понимания.

input_str = '12345555555678'
[x for x in input_str if input_str.count(x) == 1]

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

Если вы преобразуете список в набор с использованием set(input_str), тогда он будет имеют уникальные значения, которые могут существенно сократить пространство поиска.

Затем вы можете применить понимание списка.

input_str = '12345555555678'
[x for x in set(input_str) if input_str.count(x) == 1]

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