Проверьте, есть ли в списке только дублированные элементы (т.е. нет уникальных элементов)

Question

У меня есть массив с четным числом int с, и я хочу проверить, являются ли все эти элементы «парными», то есть [0, 1, 0, 1] имеет пару 1 с и пару 0 с. vs [0, 1, 1, 2] имеет только один 0 и один 2.

Моей первой мыслью было привести его к набору и проверить, имеет ли набор длину половины оригинала:

def isPaired(arr):
    return len(arr) / 2 == len(set(arr)

Но это неверно, если arr = [0, 1, 0, 0].

. Моей следующей мыслью было отсортировать массив и сравнить каждый четный индекс со следующим индексом:

def isPaired(arr):
    arr.sort
    for i in range(0, len(arr) - 1):
        if i % 2 == 0 && arr[i] != arr[i+1]:
            return False
    return True

Это работает, но время выполнения - это, по крайней мере, время выполнения такого рода. Есть ли решение этой проблемы без сортировки массива?

Answer 1

Вы можете использовать Counter следующим образом:

from collections import Counter
all(c % 2 == 0 for c in Counter([0, 1, 0, 1]).values())
# True

Вы также можете сортировать и сравнивать последовательные элементы:

l = sorted([0, 1, 0, 1])
all(x == y for x, y in zip(l[::2], l[1::2]))
# True

Сложность, предпочитайте первый вариант, так как егов худшем случае сложность только линейная.

Answer 2

Используется меньше памяти:

INPUT = [0, 1, 0 , 1]

odd = set()
for n in INPUT:
    if n in odd: 
        odd.remove(n)
    else:
        odd.add(n)

print(not odd)

Принимает [1,1,1,1] как две пары.

Answer 3

def have_pairs(a):
    temp_dict = dict()
    for i in a:
        if i in temp_dict:
            temp_dict[i] += 1
        else:
            temp_dict[i] = 1
    frequency = temp_dict.values()
    pairs = True
    for i in frequency:
        if i % 2 == 1:
            pairs = False
            break
    return pairs


a = [1, 1, 2, 3, 3, 2]
print(have_pairs(a))
# True

a = [1, 1, 2, 3, 3]
print(have_pairs(a))
# False