Как найти одинаковые элементы в строке питон

Given a string, find all the duplicate characters which are similar to each other. Let us look at the example. 

Examples:

Input : hello
Output : l

Input : geeksforgeeeks
Output : e g k s

Naive approach:

The idea is to use a dictionary to keep track of the count of each character in the input string. The program iterates through the string and adds each character to the dictionary, incrementing the count if the character is already present in the dictionary. After iterating through the string, the program then iterates through the dictionary to find characters with a count greater than 1, indicating that they are duplicates. These duplicate characters are stored in a list and returned as the output.

Implementation:

['g', 'e', 'k', 's']

Time complexity: O(n), where n is the length of the input string. 
Auxiliary space: O(k), where k is the number of distinct characters in the input string.

We have discussed a solution in the below post. Print all the duplicates in the input string We can solve this problem quickly using the python Counter() method. 

The approach is very simple. 

1. Create a dictionary using the Counter method having strings as keys and their frequencies as values.
2. Declare a temp variable.
3. Print all the indexes from the keys which have values greater than 1. 

Time Complexity: O(n), where n is the length of the string
Auxiliary Space: O(n) // since we are creating a dictionary and at worst case all elements will be stored inside it.

Approach : Using count() method

Time Complexity: O(n), where n is the length of the string
Auxiliary Space: O(n) // since we are using an extra list and in the worst case all elements will be stored inside it.

Approach : Using filter() method

Time Complexity: O(n), where n is the length of the string
Auxiliary Space: O(n)// since we are using a set to store all the values and in the worst case all elements will be stored inside it.

Using sets: 

Algorithm:

• Create two empty sets, one to store unique characters and one to store duplicate characters.
• Iterate through each character in the string.
• If the current character is already in the unique_chars set, it is a duplicate, so add it to the duplicate_chars set. 
• Otherwise, add it to the unique_chars set.
• Return the duplicate_chars 
   

{'g', 's', 'e', 'k'}

Complexity Analysis:

The time complexity of this algorithm is O(n), where n is the length of the input string. 
The space complexity is also O(n), as the worst-case scenario is that all characters in the string are unique, and therefore all characters will be added to the char_set set.

Using functools.reduce method: 

Algorithm:

• Initialize test string. 
• Using reduce method on a string which iterates over each character of a string and performs a function on a string. 
•  The function checks whether the character index from the left of the string and the right of the string is the same or not and whether it is already in the result or not.   
• If any character satisfies the above condition then it is added to the result. 
• Print the result. 

Time Complexity: O(N)  where N is the length of the string
Auxiliary Space: O(M)  M is the length of the new string.t 

Last Updated :
05 May, 2023

Like Article

Save Article

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

Вот пример такой функции:

def count_repeats(lst):
    """
    Возвращает словарь, в котором каждому элементу списка lst соответствует
    количество его повторений.
    """
    repeats = {}
    for item in lst:
        if item in repeats:
            repeats[item] += 1
        else:
            repeats[item] = 1
    return repeats



# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
repeats = count_repeats(lst)
print(repeats)  # {10: 3, 123: 2}

Функция count_repeats принимает на вход список lst, перебирает его элементы и добавляет их в словарь repeats. Если элемент уже есть в словаре, то увеличивается значение соответствующей пары ключ-значение, если же элемента еще нет в словаре, то добавляется пара с ключом равным этому элементу и значением 1.

Вы можете использовать эту функцию, чтобы найти повторяющиеся элементы в списке и количество их повторений.

Вы также можете использовать функцию Counter из модуля collections, чтобы посчитать количество повторений элементов списка. Эта функция возвращает словарь, в котором каждому элементу списка соответствует количество его повторений.

Вот пример кода, который использует функцию Counter:

from collections import Counter

def count_repeats(lst):
    """
    Возвращает словарь, в котором каждому элементу списка lst соответствует
    количество его повторений.
    """
    return Counter(lst)


# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
repeats = count_repeats(lst)
print(repeats)  # Counter({10: 3, 123: 2})

В этом коде сначала импортируется модуль collections и функция Counter, а затем определяется функция count_repeats, которая принимает список lst и возвращает результат вызова функции Counter на этом списке.

Вы также можете использовать функцию most_common из модуля collections, чтобы найти топ-N самых часто встречающихся элементов в списке. Эта функция принимает список и число N, и возвращает список кортежей, каждый из которых содержит элемент и количество его повторений.

Вот пример кода, который использует функцию most_common:

from collections import Counter

def find_top_repeats(lst, n):
    """
    Возвращает топ-N самых часто встречающихся элементов в списке lst.
    """
    return Counter(lst).most_common(n)


# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
top_repeats = find_top_repeats(lst, 2)
print(top_repeats)  # [(10, 3), (123, 2)]

В этом коде сначала импортируется модуль collections и функция Counter, а затем определяется функция find_top_repeats, которая принимает список lst и число n, и возвращает результат вызова функции most_common

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

Вот пример кода, который использует функцию set:

def find_unique(lst):
    """
    Возвращает список уникальных элементов в списке lst.
    """
    return list(set(lst))


# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
unique = find_unique(lst)
print(unique)  # [66, 78, 10, 123, 23]

В этом коде определяется функция find_unique, которая принимает список lst и возвращает список уникальных элементов. Для этого список преобразуется в множество

Если вам нужно найти только уникальные элементы в списке и посчитать их количество, то можете соединить два предыдущих подхода: сначала использовать функцию set для нахождения уникальных элементов, а затем функцию count_repeats для подсчета их количества.

Вот пример кода, который реализует этот подход:

def count_unique(lst):
    """
    Возвращает словарь, в котором каждому уникальному элементу списка lst соответствует
    количество его повторений.
    """
    repeats = {}
    for item in set(lst):
        repeats[item] = lst.count(item)
    return repeats


# Пример использования функции
lst = [10, 10, 23, 10, 123, 66, 78, 123]
unique_counts = count_unique(lst)
print(unique_counts)  # {66: 1, 78: 1, 10: 3, 123: 2}

В этом коде определяется функция count_unique, которая принимает список lst и возвращает словарь, в котором каждому уникальному элементу списка

In this tutorial, you’ll learn how to find and work with duplicates in a Python list. Being able to work efficiently with Python lists is an important skill, given how widely used lists are. Because Python lists allow us to store duplicate values, being able to identify, remove, and understand duplicate values is a useful skill to master.

By the end of this tutorial, you’ll have learned how to:

• Find duplicates in a list, as well as how to count them
• Remove duplicates in Python lists
• Find duplicates in a list of dictionaries and lists

Let’s get started!

Let’s start this tutorial by covering off how to find duplicates in a list in Python. We can do this by making use of both the set() function and the list.count() method.

The .count() method takes a single argument, the item you want to count, and returns the number of times that item appears in a list. Because of this, we can create a lists comprehension that only returns items that exist more than once. Let’s see how this works and then break it down a bit further:

# Finding Duplicate Items in a Python List
numbers = [1, 2, 3, 2, 5, 3, 3, 5, 6, 3, 4, 5, 7]

duplicates = [number for number in numbers if numbers.count(number) > 1]
unique_duplicates = list(set(duplicates))

print(unique_duplicates)

# Returns: [2, 3, 5]

Let’s break down what we did here:

1. We used a list comprehension to include any item that existed more than once in the list
2. We then converted this to a set to remove any duplicates from the filtered list
3. Finally, we converted the set back to a list

In the next section, you’ll learn how to find duplicates in a Python list and count how often they occur.

How to Find Duplicates in a List and Count Them in Python

In this section, you’ll learn how to count duplicate items in Python lists. This allows you to turn a list of items into a dictionary where the key is the list item and the corresponding value is the number of times the item is duplicated.

In order to accomplish this, we’ll make use of the Counter class from the collections module. We’ll then filter our resulting dictionary using a dictionary comprehension. Let’s take a look at the code and then we’ll break down the steps line by line:

# Finding Duplicate Items in a Python List and Count Them
from collections import Counter
numbers = [1, 2, 3, 2, 5, 3, 3, 5, 6, 3, 4, 5, 7]

counts = dict(Counter(numbers))
duplicates = {key:value for key, value in counts.items() if value > 1}
print(duplicates)

# Returns: {2: 2, 3: 4, 5: 3}

Let’s break this code down, as it’s a little more complex:

1. We import the Counter class from the collections library
2. We load our list of numbers
3. We then create a Counter object of our list and convert it to a dictionary
4. We then filter our dictionary to remove any key:value pairs where the key only exists a single time

In the next section, you’ll learn how to remove duplicates from a Python list.

How to Remove Duplicates from a List in Python

Removing duplicates in a Python list is made easy by using the set() function. Because sets in Python cannot have duplicate items, when we convert a list to a set, it removes any duplicates in that list. We can then turn the set back into a list, using the list() function.

Let’s see how we can do this in Python:

# Remove Duplicates from a List in Python
from collections import Counter
numbers = [1, 2, 3, 2, 5, 3, 3, 5, 6, 3, 4, 5, 7]
unique = list(set(numbers))
print(unique)

# Returns: [1, 2, 3, 4, 5, 6, 7]

To learn about other ways you can remove duplicates from a list in Python, check out this tutorial covering many different ways to accomplish this! In the next section, you’ll learn how to find duplicates in a list of dictionaries.

How to Remove Duplicates in a List of Dictionaries in Python

Let’s take a look at how we can remove duplicates from a list of dictionaries in Python. You’ll often encounter data from the web in formats that resembles lists of dictionaries. Being able to remove the duplicates from these lists is an important skill to simplify your data.

Let’s see how we can do this in Python by making using a for a loop:

# Remove Duplicates from a List of Dictionaries
items = [{'name':'Nik'}, {'name': 'Kate'}, {'name':'James'}, {'name':'Nik'}, {'name': 'Kate'}]
unique_items = []

for item in items:
    if item not in unique_items:
        unique_items.append(item)
print(unique_items)

# Returns: [{'name': 'Nik'}, {'name': 'Kate'}, {'name': 'James'}]

This method will only include complete duplicates. This means that if a dictionary had, say, an extra key-value pair it would be included.

How to Remove Duplicates in a List of Lists in Python

We can use the same approach to remove duplicates from a list of lists in Python. Again, this approach will require the list to be complete the same for it to be considered a duplicate. In this case, even different orders will be considered unique.

Let’s take a look at what this looks like:

# Remove Duplicates from a List of Lists in Python
list_of_lists = [[1,2,3], [1,2], [2,3], [1,2,3], [2,3], [1,2,3,4]]
unique = []

for sublist in list_of_lists:
    if sublist not in unique:
        unique.append(sublist)

print(unique)

# Returns: [[1, 2, 3], [1, 2], [2, 3], [1, 2, 3, 4]]

What we do here is loop over each sublist in our list of lists and assess whether the item exists in our unique list. If it doesn’t already exist (i.e., it’s unique so far), then it’s added to our list. This ensures that an item is only added a single time to our list.

Conclusion

In this tutorial, you learned how to work with duplicate items in Python lists. First, you learned how to identify duplicate elements and how to count how often they occur. You then learned how to remove duplicate elements from a list using the set() function. From there, you learned how to remove duplicate items from a list of dictionaries as well as a list of lists in Python.

Being able to work with lists greatly improves your Python programming skills. Because these data structures are incredibly common, being able to work with them makes you a much more confident and capable developer.

To learn more about the Counter class from the collections library, check out the official documentation here.

Additional Resources

To learn about related topics, check out the tutorials below:

• Python: Combine Lists – Merge Lists (8 Ways)
• Python: Count Number of Occurrences in List (6 Ways)
• Python List Difference: Find the Difference between 2 Python Lists

В этом посте мы обсудим, как найти повторяющиеся элементы в списке в Python.

1. Использование index() функция

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

Скачать  Выполнить код

2. Использование оператора In

Кроме того, вы можете использовать нарезку с in оператор для поиска в уже посещенной части списка. Временная сложность решения остается квадратичной и позволяет повторять элементы на выходе.

Скачать  Выполнить код

3. Использование набора (эффективно)

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

Скачать  Выполнить код

 
Чтобы получить каждый дубликат только один раз, вы можете использовать понимание множества, как показано ниже:

Скачать  Выполнить код

4. Использование count() функция

Вот альтернативное решение с использованием count() Функция, которая обеспечивает простой и понятный способ выявления дубликатов в списке. Это не рекомендуется для больших списков, поскольку временная сложность является квадратичной.

Скачать  Выполнить код

5. Использование iteration_utilities модуль

Наконец, iteration_utilities модуль предлагает duplicates функция, которая дает повторяющиеся элементы. Вы можете использовать это как:

 
Чтобы получить каждый дубликат только один раз, объедините его с unique_everseen():

Это все, что касается поиска повторяющихся элементов в списке в Python.

 
Также см:

Удалить повторяющиеся значения из списка Python