Есть ли функция Python, которая возвращает первый положительный int, которого нет в списке?

Question

Я пытаюсь разработать функцию, которая, учитывая массив A из N целых чисел, возвращает наименьшее положительное целое число (больше 0), которого нет в A.

Этот код работает нормально, но имеетвысокий уровень сложности, есть ли другое решение, которое уменьшает порядок сложности?

Примечание: число 10000000 - это диапазон целых чисел в массиве A, я пробовал функцию sort, но уменьшает ли она сложность?

def solution(A):
    for i in range(10000000):
        if(A.count(i)) <= 0:
            return(i)

Answer 1

Ниже приведено O (n logn) :

a = [2, 1, 10, 3, 2, 15]

a.sort()
if a[0] > 1:
  print(1)
else:
  for i in range(1, len(a)):
    if a[i] > a[i - 1] + 1:
      print(a[i - 1] + 1)
      break

Если вам не нравится специальная обработка 1, вы можете просто добавить ноль в массив иимеют одинаковую логику для обоих случаев:

a = sorted(a + [0])
for i in range(1, len(a)):
  if a[i] > a[i - 1] + 1:
    print(a[i - 1] + 1)
    break

Предостережения (оба несложно исправить, и оба оставлены в качестве упражнения для читателя):

• Ни одна из версий не обрабатывает пустой ввод.
• Код предполагает, что на входе нет отрицательных чисел.

Answer 2

O (n) время и O (n) пространство:

def solution(A):
    count = [0] * len(A)
    for x in A:
       if 0 < x <= len(A):
          count[x-1] = 1  # count[0] is to count 1
    for i in range(len(count)):
        if count[i] == 0:
           return i+1
    return len(A)+1  # only if A = [1, 2, ..., len(A)]

Answer 3

Вдохновленный различными решениями и комментариями выше, примерно на 20% -50% быстрее в моих (упрощенных) тестах, чем в самых быстрых из них (хотя я уверен, что это может быть сделано быстрее), и в обработке всех упомянутых угловых случаев ( неположительные числа, дубликаты и пустой список):

import numpy

def firstNotPresent(l):
    positive = numpy.fromiter(set(l), dtype=int) # deduplicate
    positive = positive[positive > 0] # only keep positive numbers
    positive.sort()
    top = positive.size + 1
    if top == 1: # empty list
        return 1
    sequence = numpy.arange(1, top)
    try:
        return numpy.where(sequence < positive)[0][0]
    except IndexError: # no numbers are missing, top is next
        return top

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

Это и другие решения, с которыми я тестировал (от adrtam , Паритош Сингх и VPfB ), все выглядят как примерно O (n), как и ожидалось. (Я думаю, довольно очевидно, что это нижняя граница, поскольку каждый элемент в списке должен быть исследован, чтобы найти ответ.) Редактировать: если посмотреть на это еще раз, конечно, большое значение для этого подхода, по крайней мере, O (n log (n)), из-за сортировки. Просто сортировка настолько быстрая, что она выглядела линейно в целом.

Answer 4

Мое предложение представляет собой рекурсивную функцию, основанную на быстрой сортировке.

Каждый шаг делит входную последовательность на два подсписка (lt = меньше, чем pivot; ge = больше или равен, чем pivot) и решает, какой из подсписковдолжен быть обработан на следующем шаге.Обратите внимание, что сортировка отсутствует.

Идея состоит в том, что набор целых чисел, такой что lo <= n <hi, содержит «пробелы» только в том случае, если в нем меньше (hi - lo) элементов. </p>

Введенная последовательность не должна содержать дублирования.Набор может быть передан напрямую.

# all cseq items > 0 assumed, no duplicates!
def find(cseq, cmin=1):
    # cmin = possible minimum not ruled out yet
    size = len(cseq)
    if size <= 1:
        return cmin+1 if cmin in cseq else cmin
    lt = []
    ge = []
    pivot = cmin + size // 2
    for n in cseq:
        (lt if n < pivot else ge).append(n)
    return find(lt, cmin) if cmin + len(lt) < pivot else find(ge, pivot)


test = set(range(1,100))
print(find(test)) # 100
test.remove(42)
print(find(test)) # 42
test.remove(1)
print(find(test)) # 1

Answer 5

Это должно быть O (n). Использует временный набор для ускорения вещей.

a = [2, 1, 10, 3, 2, 15]
#use a set of only the positive numbers for lookup

temp_set = set()
for i in a:
    if i > 0:
        temp_set.add(i)

#iterate from 1 upto length of set +1 (to ensure edge case is handled)
for i in range(1, len(temp_set) + 2):
    if i not in temp_set:
        print(i)
        break