обязательное условие - алгоритмическая сложность не должна быть O(n^2).
[
{"key1": "value1"},
{"k1": "v1", "k2": "v2", "k3": "v3"},
{},
{},
{"key1": "value1"},
{"key1": "value1"},
{"key2": "value2"}
]
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуобязательное условие - алгоритмическая сложность не должна быть O(n^2).
[
{"key1": "value1"},
{"k1": "v1", "k2": "v2", "k3": "v3"},
{},
{},
{"key1": "value1"},
{"key1": "value1"},
{"key2": "value2"}
]
Вот код, который выведет уникальные словари в порядке их появления в исходном списке.
dicts = [
{"key1": "value1"},
{"k1": "v1", "k2": "v2", "k3": "v3"},
{},
{},
{"key1": "value1"},
{"key1": "value1"},
{"key2": "value2"}
]
known_dicts = set()
result = []
for d in dicts:
items = tuple(d.items())
if items not in known_dicts:
result.append(d)
known_dicts.add(items)
print(result)
Сложность здесь точно будет субквадратичная. И, кажется, даже чуть ли не линейная, если я ничего не упускаю из вида.
O(n)
, потому что поиск в словаре при удачной хэш-функции это O(1)
.
Предложенное мной ниже решение не удовлетворяет условию: алгоритмическая сложность не должна быть O(n^2) (спасибо людям в комментариях, которые указали на ошибку) Здесь сложность будет O(n^2).
def remove_duplicate(array: List[dict]) -> List:
unique_array = []
for elem in array:
if elem not in unique_array:
unique_array.append(elem)
print(unique_array)
Всё же я хочу предложить другое решение воспользовавшись не строгостью условия о порядке элементов, предполагаю, что у данного алгоритма сложность меньше чем O(n^2):
def remove_duplicate(array: List[dict]) -> List:
unique_set = {tuple(elem.items()) for elem in array}
print([dict(elem) for elem in unique_set])
O(n)
, в отличие от поиска в словаре O(1)
из уже принятого ответа. Поскольку поиск этот производится внутри цикла, уже имеющего сложность O(n)
, поэтому ваш вариант имеет сложность O(n^2)
, в отличие от O(n)
в уже принятом ответе.