Проверка эффективности памяти, если входы были повторены

Question

Я получаю N int входы, и я хочу проверить, повторялись ли они. Простой способ - просто использовать список и проверять, содержится ли новый ввод. Однако, для моего, я знаю, что мои входные данные < N, поэтому я могу просто составить список

l = [0]*N

и затем проверить,

def getinputs(N):
    state = 1
    l = [0]*N
    for _ in range(N):
        i = int(input())
        if l[i] != 0:
           l[i] += 1
        else:
            state = 0
    return state

Проблема здесь в том, что если N >> 1, тогда размер списка очень велик, и это вызывает проблемы. Есть ли более умный способ узнать, был ли ввод повторен?

Answer 1

Используйте набор:

s = set()
s.add(3)
4 in s
# False
3 in s
# True

Это гораздо лучше, чем список для проверки повторов, поскольку это O (1), а не O (n)

Если вы хотите посчитать число повторений, используйте словарь:

d = {}
d[1] = d.get(1, 0) + 1

В словарях также есть поиск O (1)