Y a-t-il une fonction Python qui renvoie le premier entier positif qui ne se trouve pas dans la liste?

Question

Je tente de concevoir une fonction qui, étant donné un tableau A de N entiers, renvoie le plus petit entier positif (supérieur à 0) qui n'apparaît pas dans A.

Ce code fonctionne bien mais a un niveau de complexité élevé, y a-t-il une autre solution qui réduit le niveau de complexité?

Note : Le nombre 10000000 est la plage d'entiers dans le tableau A, j'ai essayé la fonction sort mais cela réduit-il la complexité?

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

Answer 1

La suite est 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

Si vous n'aimez pas la gestion spéciale de 1, vous pourriez simplement ajouter zéro au tableau et avoir la même logique pour gérer les deux cas :

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

Mises en garde (toutes deux faciles à corriger et laissées en exercice pour le lecteur):

• Aucune des versions ne gère une entrée vide.
• Le code suppose qu'il n'y a pas de nombres négatifs en entrée.

Answer 2

O(n) temps et O(n) espace:

def solution(A):
    count = [0] * len(A)
    for x in A:
       if 0 < x <= len(A):
          count[x-1] = 1  # count[0] est pour compter 1
    for i in range(len(count)):
        if count[i] == 0:
           return i+1
    return len(A)+1  # seulement si A = [1, 2, ..., len(A)]

Answer 3

Cela devrait être O(n). Utilise un ensemble temporaire pour accélérer les choses.

a = [2, 1, 10, 3, 2, 15]
#utilisez un ensemble uniquement pour les nombres positifs pour la recherche

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

#itérer de 1 jusqu'à la longueur de l'ensemble +1 (pour garantir la gestion des cas limites)
for i in range(1, len(temp_set) + 2):
    if i not in temp_set:
        print(i)
        break

Answer 4

Ma proposition est une fonction récursive inspirée de quicksort.

Chaque étape divise la séquence d'entrée en deux sous-listes (lt = moins que pivot; ge = supérieur ou égal au pivot) et décide quelle des sous-listes sera traitée à la prochaine étape. Notez qu'il n'y a pas de trie.

L'idée est qu'un ensemble d'entiers tel que lo <= n < hi ne contient que des "lacunes" s'il a moins de (hi - lo) éléments.

La séquence d'entrée ne doit pas contenir de doublons. Un ensemble peut être passé directement.

# tous les éléments de cseq > 0 sont supposés, pas de doublons !
def find(cseq, cmin=1):
    # cmin = minimum possible non encore exclu
    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

InSPIRE par diverses solutions et commentaires ci-dessus, environ 20 % - 50 % plus rapide dans mes tests (simples) que le plus rapide d'entre eux (bien que je sois sûr qu'il pourrait être rendu plus rapide), et gérant tous les cas de coin mentionnés (nombres non positifs, doublons et liste vide) :

import numpy

def firstNotPresent(l):
    positive = numpy.fromiter(set(l), dtype=int) # dédupliquer
    positive = positive[positive > 0] # ne garder que les nombres positifs
    positive.sort()
    top = positive.size + 1
    if top == 1: # liste vide
        return 1
    sequence = numpy.arange(1, top)
    try:
        return numpy.where(sequence < positive)[0][0]
    except IndexError: # aucun nombre ne manque, top est le suivant
        return top

L'idée est la suivante : si vous énumérez la liste triée, dédupliquée et positive à partir de un, la première fois que l'index est inférieur à la valeur de la liste, la valeur de l'index manque dans la liste et est donc le plus petit nombre positif manquant dans la liste.

Ce code et les autres solutions que j'ai testées (celles de adrtam, Paritosh Singh et VPfB) semblent toutes être environ O(n), comme prévu. (Je pense que c'est assez évident que c'est une borne inférieure, puisque chaque élément de la liste doit être examiné pour trouver la réponse.) Édition : En y repensant, bien sûr, le grand O pour cette approche est au moins O(n log(n)), en raison du tri. C'est juste que le tri est tellement rapide en comparaison qu'il semblait linéaire dans l'ensemble.