Как получить наименьшее целое число, не представленное в массиве

Question

Я пытаюсь найти наименьшее положительное число, которого нет в списке a

def smallitem(a):
    a = sorted(set(a))
    lst = []
    for item in a:
        item + = 1
        if item not in a:
        lst.append(item)
        continue
    mst = []
    for item in lst:
        if item < 1:
            item += 1
            if item not in a:
                mst.append(item)
                continue
    n = 0
    if mst:
        n = min(mst)
    return n or min(lst)

Я думаю, что у меня есть решение, но оно мне не кажется правильным, как я это сделал.

например:

smallitem([-1, -3]) # 1

smallitem([1,3,6,4,1,2, 87]) # 5

Answer 1

Возможно, есть более легкий способ сделать это.Временная сложность всегда O (n).

def small_item(a):
    s = set(a)
    for i in range(1, max(s)):
        if i not in s:
            return i
    return max(max(s) + 1, 1)

print small_item([1,3,6,4,1,2, 87])
print small_item([-1, -3])

Answer 2

Вот другой способ сделать это:

def smallitem(l):
    l = list(set(sorted(l)))
    x = l[0]
    for i in l:
        if i != x and x >= 1:return x
        x += 1
    return 1

Тестирование:

>>> smallitem([-3, -1])
1
>>> smallitem([1, 3, 6, 4, 1, 2, 87])
5
>>> 

Answer 3

Вы можете преобразовать список в набор, а затем продолжать увеличивать положительное целое число от 1 до тех пор, пока он не будет найден в наборе:

def smallitem(a):
    set_a = set(a)
    i = 1
    while i in set_a:
        i += 1
    return i