0

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

[
    {"key1": "value1"},
    {"k1": "v1", "k2": "v2", "k3": "v3"},
    {},
    {},
    {"key1": "value1"},
    {"key1": "value1"},
    {"key2": "value2"}
]
2
  • O(n^2) - означает, что ты можешь использовать цикл внутри цикла. Пробегись по всем элементам и сравни каждый с каждым.
    – Sergey K.
    11 ноя 2022 в 19:44
  • @SergeyK. автор же наоборот пишет, что такая сложность быть не должна.
    – Xander
    11 ноя 2022 в 20:53

2 ответа 2

1

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

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)

Сложность здесь точно будет субквадратичная. И, кажется, даже чуть ли не линейная, если я ничего не упускаю из вида.

2
  • Спасибо за ответ.
    – samsegomof
    12 ноя 2022 в 17:55
  • 1
    Да, сложность тут O(n), потому что поиск в словаре при удачной хэш-функции это O(1).
    – CrazyElf
    23 янв в 12:07
0

Предложенное мной ниже решение не удовлетворяет условию: алгоритмическая сложность не должна быть 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])
3
  • 1
    Что такое "понимание списка"? Почему вы думаете, что временная сложность O (n)???
    – MBo
    23 янв в 10:32
  • Поиск в списке имеет сложность O(n), в отличие от поиска в словаре O(1) из уже принятого ответа. Поскольку поиск этот производится внутри цикла, уже имеющего сложность O(n), поэтому ваш вариант имеет сложность O(n^2), в отличие от O(n) в уже принятом ответе.
    – CrazyElf
    23 янв в 12:06
  • Да, действиетельно, моя ошибка, спасибо за комментарии сложность будет O(n^2). Предлагаю другое решение
    – MrRom4ke
    25 янв в 14:38

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.