Python уникальные значения строки

Определяем, все ли символы в строке уникальны. Разбор задачи

Давайте решим простую задачку, связанную с обработкой строк в Python.

# Определите, все ли символы в строке уникальны. # Использовать дополнительные структуры данных нельзя.

Довольно просто, верно? Это, собственно, первое задание из раздела «Массивы и строки» в книге «Cracking the Coding Interview». При решении этой задачи мы можем применить разные подходы, причем пространственная и временная сложность в них будет отличаться. Давайте рассмотрим парочку вариантов.

Первый подход: брутфорс

Брутфорс (англ. brute force — грубая сила) — это обычно самый простой способ решения любой задачи на белой доске, так что будет полезным начать именно с него. Имея брутфорс-решение, мы сможем воспользоваться хотя бы им, если более элегантные методы не сработают. Также это хорошая практика в основах программирования. Читая это решение, вы лучше поймете, с какого конца вообще надо браться за задачи.

Название «брутфорс» говорит само за себя. Представьте, что у вас есть набор пазлов, где все кусочки одного цвета. Вам придется вслепую пробовать каждую комбинацию, пока не найдете пару пазлов, которые можно соединить. Что касается нашей задачи, мы будем сверять каждый символ в строке со всеми остальными, пытаясь найти совпадения.

Начнем с определения метода (можете работать в Repl.it, а можете воспользоваться просто карандашом и бумагой). Наш метод будет принимать одну строку в качестве параметра. Ее мы обозначим как s .

Дальше мы определим наш первый цикл for . Вообще у нас будут вложенные циклы, а этот будет перебирать все символы в строке до предпоследнего (включительно). Почему не до последнего? Потому что каждый из этих символов мы будем сравнивать с теми, которые идут после него, а за последним больше нет других символов.

def is_unique(s): for i in range(len(s) - 1):

Теперь давайте сделаем второй цикл for внутри первого. Он будет начинаться от следующей позиции в списке, которой мы назначим индекс j . Индекс j будет расти до конца списка, а элементы под этим индексом будут сравниваться с символом под индексом i . В случае совпадения мы вернем False — это будет означать, что не все символы в строке уникальны.

def is_unique(s): for i in range(len(s) - 1): for j in range(i + 1, len(s)): if s[j] == s[i]: return False

Наконец, нам нужно где-нибудь вернуть True. Если вложенный цикл for успешно сравнил все символы и не нашел совпадений, значит, все символы в строке уникальны. Поэтому мы возвращаем True за пределами вложенного цикла.

def is_unique(s): for i in range(len(s) - 1): for j in range(i + 1, len(s)): if s[j] == s[i]: return False return True

Вот и все! Вызов is_unique(«Hello») должен вернуть False, а is_unique(«Bye») — True.

Временная и пространственная сложность брутфорс-метода

Прежде всего, наше решение удовлетворяет требованию «никаких дополнительных структур данных». Мы просто перебираем в цикле строку, не сохраняя информацию в новой структуре. Это дает нам пространственную сложность O(1), которая не зависит от длины строки.

Как насчет временной сложности? Представим наихудший случай. В строке нет уникальных символов, поэтому вложенный цикл отрабатывает все до конца. Временная сложность здесь будет примерно O(N2), несмотря на то, что мы экономим некоторое время, проверяя каждую пару только единожды. O(N2) это ужасно. Но это, вероятно, наилучший вариант, если нельзя создавать дополнительные структуры данных или модифицировать исходную строку.

Более оптимальный подход: сортировка строки

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

Метод Python .sort() работает только со списками. Так что наша первая задача — превратить строку в список символов. Мы показываем, как это делается, что если вы дойдете до собеседования с решением задач у доски, такие вещи у вас должны уже от зубов отскакивать.

s_as_list = [char for char in s]

Цикл for перебирает все символы в строке s и возвращает каждый символ. Мы записываем результат в список, взяв цикл в квадратные скобки.

Превратив строку в список, мы можем вызвать метод sort() .

def is_unique2(s): s_as_list = [char for char in s] s_as_list.sort()

Теперь мы можем перебрать список. Мы будем сравнивать каждую букву с предыдущей. Сделать это можно двумя способами. Можно проитерировать каждый индекс, с первого (если таковой существует) до последнего. А если не отслеживать индекс, можно сохранять предыдущую букву в переменную. Инициализировать переменную можно как пустую строку.

prev = "" for letter in s_as_list:

На каждой итерации нам нужно сделать одно из двух:

1. Если символ такой же, как и предыдущий, вернуть False.
2. В противном случае сделать этот символ новым предыдущим символом.

Можно превратить это в предложение if . Давайте используем в качестве имени переменной letter , а не char , чтобы не путать с тем, что мы делали ранее, когда превращали строку в список.

prev = "" for letter in s_as_list: if letter == prev: return False else: prev = letter

Наконец, если цикл for успешно отработает и не найдет совпадений, мы вернем True за пределами цикла. Все вместе это выглядит так:

def is_unique2(s): s_as_list = [char for char in s] s_as_list.sort() prev = "" for letter in s_as_list: if letter == prev: return False else: prev = letter return True

Временная сложность решения с использованием метода sort()

Временная сложность этого решения зависит от временной сложности самого метода sort(). Python использует Timsort — гибрид сортировки слиянием и вставками (если вам это о чем-то говорит). Его временная сложность в среднем и наихудшем случае — O(N log N). Кроме того, мы перебираем список в цикле N раз, но этим можно пренебречь, потому что O(N log N) больше.

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

Решение, еще более оптимальное с точки зрения временной сложности: использование словаря

Давайте вообще отбросим запрет на дополнительные структуры данных. Какое решение еще можно предложить в таком случае? В книге Cracking the Coding Interview первое решение предполагает использование массива с длиной 128 (длина всего алфавита Unicode). Но если вы уже пользовались Python пару раз, вы, вероятно, знакомы с такой структурой как словарь.

В Python есть библиотека с дефолтным словарем — defaultdict. Она позволяет нам задавать значения по умолчанию: при вызове ключа, которого нет в словаре, будет создана пара из этого ключа и дефолтного значения. Это избавляет нас от необходимости проверять, есть ли ключ в списке, перед поиском его значения.

Мы можем назначить нашему словарю dd тип bool , таким образом дефолтное значение всегда будет False.

from collections import defaultdict def is_unique3(s): dd = defaultdict(bool)

Теперь давайте напишем цикл for . Мы переберем в цикле все символы в строке, проверяя их значение. Если значение будет True, это будет означать, что такой символ нам уже попадался. В таком случае мы вернем False. Если значение будет False (а defaultdict «выдаст» его любому ключу, которого еще нет в словаре), мы присвоим этому символу значение True.

for char in s: if dd[char]: return False dd[char] = True

Наконец, мы вернем True за пределами цикла, если каждый символ встретится только один раз.

Все вместе это выглядит следующим образом:

def is_unique3(s): dd = defaultdict(bool) for char in s: if dd[char]: return False dd[char] = True return True

Временная сложность решения со словарем

Мы перебираем список N раз, кроме того доступ к каждому элементу словаря имеет временную сложность O(1). Таким образом временная сложность этого решения — O(N), а это даже лучше, чем в предыдущем способе. Работая над программами, вы увидите, что компромиссы с пространственной и временной сложностью — ваши постоянные спутники, а то, какое решение считать наилучшим, зависит от ситуации.

Источник

Как получить уникальные элементы списка python

Предположим, есть список, который содержит повторяющиеся числа:

Но нужен список с уникальными числами:

Есть несколько вариантов, как можно получить уникальные значения. Разберем их.

Вариант №1. Использование множества (set) для получения элементов

Использование множества ( set ) — один из вариантов. Он удобен тем, что включает только уникальные элементы. После этого множество можно обратно превратить в список.

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

 
numbers = [1, 2, 2, 3, 3, 4, 5] 
 
def get_unique_numbers(numbers): 
list_of_unique_numbers = [] 
unique_numbers = set(numbers) 
 
for number in unique_numbers: 
list_of_unique_numbers.append(number) 
 
return list_of_unique_numbers 
 
print(get_unique_numbers(numbers)) 
 
Разберем, что происходит на каждом этапе. Есть список чисел numbers . Передаем его в функцию get_unique_numbers .
 
Внутри этой функции создается пустой список, который в итоге будет включать все уникальные числа. После этого используется set для получения уникальных чисел из списка numbers .
 
 
unique_numbers = set(numbers) 
 
В итоге имеется перечень из уникальных чисел. Осталось сделать из него список. Для этого можно использовать цикл, перебирая каждый из элементов.
 
 
for number in unique_numbers: 
list_of_unique_numbers.append(number) 
 
На каждой итерации текущее число добавляется в список list_of_unique_numbers . Наконец, именно этот список возвращается в конце программы.
 
Есть и более короткий способ использования множества для получения уникальных значений в Python. О нем и пойдет речь дальше.
 
Короткий вариант с set
 
Весь код выше можно сжать в одну строку с помощью встроенных в Python функций.
 
 
numbers = [1, 2, 2, 3, 3, 4, 5] 
unique_numbers = list(set(numbers)) 
print(unique_numbers) 
 
Хотя этот код сильно отличается от первого примера, идея та же. Сперва множество используется для получения уникальных значений. После этого множество превращается в список.
 
 
unique_numbers = list(set(numbers)) 
 
Проще всего думать «изнутри наружу» при чтении этого кода. Самый вложенный код выполняется первым: set(numbers) . Затем — внешний блок: list(set(numbers)) .
 
Вариант №2. Использование цикла for
 
Также стоит рассмотреть подход с использованием цикла.
 
Для начала нужно создать пустой список, который будет включать уникальные числа. После этого можно задействовать цикл для итерации по каждому числу в переданном списке. Если число из него есть в уникальном, то можно переходить к следующему элементу. В противном случае — добавить это число.
 
Рассмотрим два способа использования цикла. Начнем с более подробного.
 
 
numbers = [20, 20, 30, 30, 40] 
 
def get_unique_numbers(numbers): 
unique = [] 
 
for number in numbers: 
if number in unique: 
continue 
else: 
unique.append(number) 
return unique 
 
print(get_unique_numbers(numbers)) 
 
Вот что происходит на каждом этапе. Сначала есть список чисел numbers . Он передается в функцию get_unique_numbers .
 
Внутри этой функции создается пустой список unique . В итоге он будет включать все уникальные значения.
 
Цикл будет использоваться для перебора по числам в списке numbers .
 
 
for number in numbers: 
if number in unique: 
continue 
else: 
unique.append(number) 
 
Условные конструкции в цикле проверяют, есть ли число текущей итерации в списке unique . Если да, то цикл переходит на следующую итерации. Если нет — число добавляется в список.
 
Важно отметить, что добавляются только уникальные числа. Когда цикл завершен, список unique с уникальными числами возвращается.
 
Короткий способ с циклом
 
Есть и другой способ использования варианта с циклом, который короче на несколько строк.
 
 
numbers = [20, 20, 30, 30, 40] 
 
def get_unique_numbers(numbers): 
unique = [] 
for number in numbers: 
if number not in unique: 
unique.append(number) 
return unique 
 
Разница в условной конструкции. В этот раз она следующая — если числа нет в unique , то его нужно добавить.
 
 
if number not in unique: 
unique.append(number) 
 
В противном случае цикл перейдет к следующему числу в списке numbers .
 
Результат будет тот же. Но иногда подобное читать сложнее, когда булево значение опускается.
 
Есть еще несколько способов поиска уникальных значений в списке Python. Но достаточно будет тех, которые описаны в этой статье.
 
Обучение с трудоустройством
 
Я создал этот блог в 2018 году, чтобы распространять полезные учебные материалы, документации и уроки на русском. На сайте опубликовано множество статей по основам python и библиотекам, уроков для начинающих и примеров написания программ.
 
 
Python Q CEO Pythonru admin@pythonru.com https://secure.gravatar.com/avatar/b16f253879f7349f64830c64d1da4415?s=96&d=mm&r=g CEO Pythonru Python Александр Редактор https://t.me/cashncarryhttps://pythonru.com/https://yandex.ru/q/profile/cashnc/ PythonRu.com admin@pythonru.com Alex Zabrodin 2018-10-26 Online Python, Programming, HTML, CSS, JavaScript 
 
Источник