Удаление одинаковых элементов в отсортированном листе (списке)

#python #алгоритм #list

Например, у меня есть лист x = [a, a, a, f, h, k, k]. Мне надо сделать, что бы в
этом листе было только одно a и одно k, т.е. удалить лишние похожие элементы, остальные
не трогать. Похожие элементы всегда рядом, т.к. лист просортирован. Как реализовать
удаление этих лишних элементов?
    

Ответы

Ответ 1

Можно использовать модуль itertools:

from itertools import groupby

x = ['a', 'a', 'a', 'f', 'h', 'k', 'k']

new_x = [el for el, _ in groupby(x)]

print(new_x)    # ['a', 'f', 'h', 'k']


Способ лучше варианта с set тем, что itertools.groupby сохраняет тот порядок, в котором
элементы шли в изначальной последовательности. В то время, как set не гарантирует сохранения
порядка.


Ответ 2

Проще всего так:

>>> l = [1, 1, 2, 3, 3, 5]
>>> print list(set(l))
[1, 2, 3, 5]
>>>


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

>>> l = [1, 1, 2, 3, 3, [4, 5, 6]]
>>> print list(set(l))
Traceback (most recent call last):
  File "", line 1, in 
TypeError: unhashable type: 'list'


Универсальный способ:

def f(l):
    n = []
    for i in l:
        if i not in n:
            n.append(i)
    return n


print f([1, 1, 2, 3, 3, [4, 5, 6]]) # [1, 2, 3, [4, 5, 6]]
print f([[1, 2], [1, 2], 3, 4, 4, 'oops', 'oops']) # [[1, 2], 3, 4, 'oops']




Если (как в условии) входящий список так или иначе отсортирован, в последнем алгоритме
(функция f) вместо

if i not in n:
   n.append(i)


можно написать

if not n or i != n[-1]:
   n.append(i)


что существенно улучшит эффективность.


Ответ 3

import itertools
x = 2, 2, 4, 3, 3, 1, 1, 2, 5, 4, 2, 1
print('data1:', x)


# простой спрособ - set, но теряется сортировка исходного списка
r = set(x)
print('set:', r)


# способ groupby подходит не совсем, тк уникальны только элементы идущие подряд
r = [a[0] for a in itertools.groupby(x)]
print('неверно groupby no sort:', r)

r = set(a[0] for a in itertools.groupby(x))
print('верно groupby no sort:', r)

# если список сначала отсортировать
r = [a[0] for a in itertools.groupby(sorted(x))]
print('groupby sort:', r)


# способ при котором не теряется сортировка исходного списка
def unique(obj: iter):
    args = []
    for a in obj:
        if a not in args:
            args.append(a)
            yield a

r = unique(x)
print('original sort unique:', *r)


# если список вложенный и заранее неизвесна степень вложенности
x = 2, (2, 4), [3], [3, [1, [1, 2, ([5],)], [4]], 2, 1]
print('\ndata2:', x)

def unpack(obj: iter):
    for o in obj:
        if isinstance(o, (list, tuple)):
            yield from unpack(o)
        else: yield o

r = unique(unpack(x))
print('unpack', *r)


out:

data1: (2, 2, 4, 3, 3, 1, 1, 2, 5, 4, 2, 1)
set: {1, 2, 3, 4, 5}
неверно groupby no sort: [2, 4, 3, 1, 2, 5, 4, 2, 1]
верно groupby no sort: {1, 2, 3, 4, 5}
groupby sort: [1, 2, 3, 4, 5]
original sort unique: 2 4 3 1 5

data2: (2, (2, 4), [3], [3, [1, [1, 2, ([5],)], [4]], 2, 1])
unpack 2 4 3 1 5


Ответ 4

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

x = ['a', 'a', 'a', 'f', 'h', 'k', 'k', 1]

r = [x[0]]
i = 1
j = 0
while i < len(x):
    if r[j] != x[i]:
        r.append(x[i])
        j += 1
    i += 1

print r


Ответ 5

Если использовать множество для получения списка уникальных элементов, то для получения
списка с сохранением порядка следования элементов, можно использовать сортировку по
индексу изначального списка. К примеру так:  

x = [a, a, a, f, h, k, k]
y = sorted(set(x), key=lambda d: x.index(d))
print(y)  # [a, f, h, k]


Ответ 6

Зачем такие сложности)))

l = [1, 2, 3, 4, 4, 4]
 print(list(set(l)))