Rechercher le plus petit entier ne figurant pas dans une liste

Une question d'entrevue intéressante qu'un de mes collègues utilise:

Supposons que l'on vous donne une très longue liste non triée d'entiers 64 bits non signés. Comment trouveriez-vous le plus petit entier non négatif qui n'apparaît pas dans la liste?

SUIVI: Maintenant que la solution évidente par le tri a été proposée, pouvez-vous le faire plus rapidement que O (n log n)?

SUIVI: votre algorithme doit s'exécuter sur un ordinateur avec, par exemple, 1 Go de mémoire

CLARIFICATION: La liste est en RAM, bien qu'elle puisse en consommer une grande quantité. On vous donne la taille de la liste, disons N, à l'avance.

Si la structure de données peut être mutée sur place et prend en charge l'accès aléatoire, vous pouvez le faire en temps O (N) et en espace supplémentaire O (1). Parcourez simplement le tableau de manière séquentielle et pour chaque index, écrivez la valeur à l'index de l'index spécifié par valeur, en plaçant de manière récursive toute valeur à cet emplacement à sa place et en jetant les valeurs> N. Ensuite, parcourez à nouveau le tableau à la recherche de l'endroit où la valeur ne correspond pas à l'index - c'est la plus petite valeur ne figurant pas dans le tableau. Il en résulte au plus des comparaisons 3N et n'utilise que quelques valeurs représentant un espace temporaire.

# Pass 1, move every value to the position of its value
for cursor in range(N):
    target = array[cursor]
    while target < N and target != array[target]:
        new_target = array[target]
        array[target] = target
        target = new_target

# Pass 2, find first location where the index doesn't match the value
for cursor in range(N):
    if array[cursor] != cursor:
        return cursor
return N

Voici une O(N)solution simple qui utilise l' O(N)espace. Je suppose que nous limitons la liste d'entrée aux nombres non négatifs et que nous voulons trouver le premier nombre non négatif qui n'est pas dans la liste.

1. Trouvez la longueur de la liste; disons que c'est N.
2. Alloue un tableau de Nbooléens, initialisé à tous false.
3. Pour chaque nombre Xde la liste, si Xest inférieur à N, définissez l' X'thélément du tableau sur true.
4. Parcourez le tableau à partir de l'index 0, à la recherche du premier élément false. Si vous trouvez le premier falseà l'index I, alors Iest la réponse. Sinon (c'est-à-dire lorsque tous les éléments le sont true), la réponse est N.

En pratique, le "tableau de Nbooléens" serait probablement codé comme un "bitmap" ou un "jeu de bits" représenté par un tableau byteou int. Cela utilise généralement moins d'espace (selon le langage de programmation) et permet falsed'effectuer plus rapidement l'analyse du premier .

C'est comment / pourquoi l'algorithme fonctionne.

Supposons que les Nnombres de la liste ne soient pas distincts ou qu'un ou plusieurs d'entre eux soient supérieurs à N. Cela signifie qu'il doit y avoir au moins un nombre dans la plage 0 .. N - 1qui n'est pas dans la liste. Le problème de trouver le plus petit nombre manquant doit donc se réduire au problème de trouver le plus petit nombre manquant inférieur àN . Cela signifie que nous n'avons pas besoin de garder une trace des nombres supérieurs ou égaux à N... car ils ne seront pas la réponse.

L'alternative au paragraphe précédent est que la liste est une permutation des nombres de 0 .. N - 1. Dans ce cas, l'étape 3 définit tous les éléments du tableau sur true, et l'étape 4 nous indique que le premier nombre «manquant» est N.

La complexité de calcul de l'algorithme est O(N)avec une constante de proportionnalité relativement petite. Il effectue deux passages linéaires dans la liste, ou un seul passage si la longueur de la liste est connue pour commencer. Il n'est pas nécessaire de représenter l'ensemble de la liste en mémoire, de sorte que l'utilisation asymptotique de la mémoire de l'algorithme est exactement ce qui est nécessaire pour représenter le tableau de booléens; c'est-à-dire des O(N)bits.

(En revanche, les algorithmes qui reposent sur le tri ou le partitionnement en mémoire supposent que vous pouvez représenter la liste entière en mémoire. Dans la forme où la question a été posée, cela nécessiterait O(N)des mots de 64 bits.)

@Jorn commente que les étapes 1 à 3 sont une variante du tri par comptage. Dans un sens, il a raison, mais les différences sont importantes:

• Un tri par comptage nécessite un tableau de (au moins) Xmax - Xmincompteurs où Xmaxest le plus grand nombre de la liste et Xminle plus petit nombre de la liste. Chaque compteur doit pouvoir représenter N états; c'est-à-dire en supposant une représentation binaire, il doit avoir un type entier (au moins) ceiling(log2(N))bits.
• Pour déterminer la taille du tableau, un tri par comptage doit effectuer un premier passage dans la liste pour déterminer Xmaxet Xmin.
• L'espace minimal requis dans le pire des cas est donc de ceiling(log2(N)) * (Xmax - Xmin)bits.

En revanche, l'algorithme présenté ci-dessus nécessite simplement des Nbits dans le pire et le meilleur des cas.

Cependant, cette analyse conduit à l'intuition que si l'algorithme effectuait un premier passage dans la liste à la recherche d'un zéro (et en comptant les éléments de la liste si nécessaire), il donnerait une réponse plus rapide en utilisant aucun espace du tout s'il trouvait le zéro. Cela vaut vraiment la peine de le faire s'il y a une forte probabilité de trouver au moins un zéro dans la liste. Et cette passe supplémentaire ne change pas la complexité globale.

EDIT: J'ai changé la description de l'algorithme pour utiliser "tableau de booléens" car les gens ont apparemment trouvé ma description originale utilisant des bits et des bitmaps pour être déroutante.

Étant donné que l'OP a maintenant spécifié que la liste d'origine est conservée dans la RAM et que l'ordinateur ne dispose que, disons, de 1 Go de mémoire, je vais prendre des précautions et prédire que la réponse est zéro.

1 Go de RAM signifie que la liste peut contenir au plus 134 217 728 numéros. Mais il y a 2 ⁶⁴ = 18,446,744,073,709,551,616 nombres possibles. Ainsi, la probabilité que zéro soit dans la liste est de 1 sur 137 438 953 472.

En revanche, mes chances d'être frappé par la foudre cette année sont de 1 sur 700 000. Et mes chances d' être touché par une météorite sont d'environ 1 sur 10 billions. Je suis donc environ dix fois plus susceptible d'être écrit dans une revue scientifique en raison de ma mort prématurée par un objet céleste que la réponse n'étant pas zéro.

Comme indiqué dans d'autres réponses, vous pouvez faire un tri, puis simplement scanner jusqu'à ce que vous trouviez un espace.

Vous pouvez améliorer la complexité algorithmique en O (N) et conserver l'espace O (N) en utilisant un QuickSort modifié où vous éliminez les partitions qui ne sont pas des candidats potentiels pour contenir l'écart.

• Lors de la première phase de partition, supprimez les doublons.
• Une fois le partitionnement terminé, regardez le nombre d'éléments dans la partition inférieure
• Cette valeur est-elle égale à la valeur utilisée pour créer la partition?
  • Si tel est le cas, cela implique que l'écart se situe dans la partition supérieure.
    • Continuez avec le tri rapide, en ignorant la partition inférieure
  • Sinon, l'écart est dans la partition inférieure
    • Continuez avec le tri rapide, en ignorant la partition supérieure

Cela permet d'économiser un grand nombre de calculs.

Pour illustrer l'un des pièges de la O(N)réflexion, voici un O(N)algorithme qui utilise l' O(1)espace.

for i in [0..2^64):
  if i not in list: return i

print "no 64-bit integers are missing"

Puisque les nombres ont tous une longueur de 64 bits, nous pouvons utiliser le tri par base sur eux, qui est O (n). Triez-les, puis scannez-les jusqu'à ce que vous trouviez ce que vous cherchez.

si le plus petit nombre est zéro, scannez vers l'avant jusqu'à ce que vous trouviez un espace. Si le plus petit nombre n'est pas zéro, la réponse est zéro.

Pour une méthode efficace d'espace et toutes les valeurs sont distinctes, vous pouvez le faire dans l'espace O( k )et le temps O( k*log(N)*N ). C'est peu encombrant et il n'y a pas de déplacement de données et toutes les opérations sont élémentaires (ajout de soustraction).

1. ensemble U = N; L=0
2. Commencez par partitionner l'espace numérique en krégions. Comme ça:
   • 0->(1/k)*(U-L) + L, 0->(2/k)*(U-L) + L, 0->(3/k)*(U-L) + L...0->(U-L) + L
3. Trouvez le nombre de nombres ( count{i}) dans chaque région. ( N*kétapes)
4. Trouvez la première région ( h) qui n'est pas pleine. Cela veut dire count{h} < upper_limit{h}. ( kétapes)
5. si h - count{h-1} = 1tu as ta réponse
6. ensemble U = count{h}; L = count{h-1}
7. aller à 2

cela peut être amélioré en utilisant le hachage (merci pour Nic cette idée).

1. même
2. Commencez par partitionner l'espace numérique en krégions. Comme ça:
   • L + (i/k)->L + (i+1/k)*(U-L)
3. inc count{j} en utilisant j = (number - L)/k (if L < number < U)
4. trouver la première région ( h) qui ne contient pas k éléments
5. si count{h} = 1h est ta réponse
6. ensemble U = maximum value in region h L = minimum value in region h

Cela fonctionnera O(log(N)*N).

Je les trierais simplement puis je parcourais la séquence jusqu'à ce que je trouve un espace (y compris l'écart au début entre zéro et le premier nombre).

En termes d'algorithme, quelque chose comme ça le ferait:

def smallest_not_in_list(list):
    sort(list)
    if list[0] != 0:
        return 0
    for i = 1 to list.last:
        if list[i] != list[i-1] + 1:
            return list[i-1] + 1
    if list[list.last] == 2^64 - 1:
        assert ("No gaps")
    return list[list.last] + 1

Bien sûr, si vous avez beaucoup plus de mémoire que CPU grunt, vous pouvez créer un masque de bits de toutes les valeurs 64 bits possibles et définir simplement les bits pour chaque nombre de la liste. Recherchez ensuite le premier 0 bit dans ce masque de bits. Cela en fait une opération O (n) en termes de temps mais assez chère en termes de besoins en mémoire :-)

Je doute que vous puissiez améliorer O (n) car je ne vois pas de moyen de le faire qui n'implique pas de regarder chaque nombre au moins une fois.

L'algorithme pour celui-là serait du type:

def smallest_not_in_list(list):
    bitmask = mask_make(2^64) // might take a while :-)
    mask_clear_all (bitmask)
    for i = 1 to list.last:
        mask_set (bitmask, list[i])
    for i = 0 to 2^64 - 1:
        if mask_is_clear (bitmask, i):
            return i
    assert ("No gaps")

Triez la liste, regardez les premier et deuxième éléments et commencez à remonter jusqu'à ce qu'il y ait un espace.

Vous pouvez le faire dans un temps O (n) et un espace supplémentaire O (1), bien que le facteur caché soit assez important. Ce n'est pas un moyen pratique de résoudre le problème, mais cela peut néanmoins être intéressant.

Pour chaque entier 64 bits non signé (par ordre croissant), parcourez la liste jusqu'à ce que vous trouviez l'entier cible ou que vous atteigniez la fin de la liste. Si vous atteignez la fin de la liste, l'entier cible est le plus petit entier ne figurant pas dans la liste. Si vous atteignez la fin des entiers 64 bits, chaque entier 64 bits est dans la liste.

Le voici en tant que fonction Python:

def smallest_missing_uint64(source_list):
    the_answer = None

    target = 0L
    while target < 2L**64:

        target_found = False
        for item in source_list:
            if item == target:
                target_found = True

        if not target_found and the_answer is None:
            the_answer = target

        target += 1L

    return the_answer

Cette fonction est volontairement inefficace pour la garder O (n). Notez en particulier que la fonction continue de vérifier les entiers cibles même après avoir trouvé la réponse. Si la fonction retournait dès que la réponse était trouvée, le nombre d'exécutions de la boucle externe serait lié par la taille de la réponse, qui est liée par n. Ce changement rendrait le temps d'exécution O (n ^ 2), même si ce serait beaucoup plus rapide.

Merci à egon, swilden et Stephen C pour mon inspiration. Tout d'abord, nous connaissons les limites de la valeur de l'objectif car elle ne peut pas être supérieure à la taille de la liste. En outre, une liste de 1 Go peut contenir au plus 134217728 (128 * 2 ^ 20) entiers 64 bits.

Partie de hachage
Je propose d'utiliser le hachage pour réduire considérablement notre espace de recherche. Tout d'abord, racine carrée la taille de la liste. Pour une liste de 1 Go, c'est N = 11586. Configurez un tableau d'entiers de taille N. Parcourez la liste et prenez la racine carrée * de chaque nombre que vous trouvez comme votre hachage. Dans votre table de hachage, incrémentez le compteur de ce hachage. Ensuite, parcourez votre table de hachage. Le premier compartiment que vous trouvez qui n'est pas égal à sa taille maximale définit votre nouvel espace de recherche.

Partie bitmap
maintenant régulière égale à la taille de votre nouvel espace de recherche, puis parcourez à nouveau la liste source, en remplissant la bitmap lorsque vous trouvez chaque numéro dans votre espace de recherche. Lorsque vous avez terminé, le premier bit non défini dans votre bitmap vous donnera votre réponse.

Ceci sera complété en temps O (n) et en espace O (sqrt (n)).

(* Vous pouvez utiliser quelque chose comme le décalage de bits pour le faire beaucoup plus efficacement, et simplement varier le nombre et la taille des seaux en conséquence.)

Eh bien, s'il n'y a qu'un seul nombre manquant dans une liste de nombres, le moyen le plus simple de trouver le nombre manquant est de additionner la série et de soustraire chaque valeur de la liste. La valeur finale est le nombre manquant.

 int i = 0;
            while ( i < Array.Length)
            {

                if (Array[i] == i + 1)
                {
                    i++;
                }

                if (i < Array.Length)
                {
                    if (Array[i] <= Array.Length)
                    {//SWap

                        int temp = Array[i];
                        int AnoTemp = Array[temp - 1];
                        Array[temp - 1] = temp;
                        Array[i] = AnoTemp;

                    }
                    else
                       i++;



                }
            }

            for (int j = 0; j < Array.Length; j++)
            {
                if (Array[j] > Array.Length)
                {
                    Console.WriteLine(j + 1);
                    j = Array.Length;
                }
                else
                    if (j == Array.Length - 1)
                        Console.WriteLine("Not Found !!");

            }
        }

Nous pourrions utiliser une table de hachage pour contenir les nombres. Une fois tous les nombres terminés, lancez un compteur de 0 jusqu'à ce que nous trouvions le plus bas. Un hachage raisonnablement bon hachera et stockera en temps constant, et récupère en temps constant.

for every i in X         // One scan Θ(1)
   hashtable.put(i, i);  // O(1)

low = 0;

while (hashtable.get(i) <> null)   // at most n+1 times
   low++;

print low;

Le pire des cas s'il y a des néléments dans le tableau et le sont {0, 1, ... n-1}, auquel cas, la réponse sera obtenue à n, en la conservant toujours O(n).

Voici ma réponse écrite en Java:

Idée de base: 1- Faites une boucle dans le tableau en jetant les nombres positifs, zéros et négatifs en double tout en résumant le reste, en obtenant également le nombre positif maximum et en conservant les nombres positifs uniques dans une carte.

2- Calculez la somme comme max * (max + 1) / 2.

3- Trouvez la différence entre les sommes calculées aux étapes 1 et 2

4- Bouclez à nouveau de 1 au minimum de [somme différence, max] et retournez le premier nombre qui ne se trouve pas dans la carte renseignée à l'étape 1.

public static int solution(int[] A) {
    if (A == null || A.length == 0) {
        throw new IllegalArgumentException();
    }

    int sum = 0;
    Map<Integer, Boolean> uniqueNumbers = new HashMap<Integer, Boolean>();
    int max = A[0];
    for (int i = 0; i < A.length; i++) {
        if(A[i] < 0) {
            continue;
        }
        if(uniqueNumbers.get(A[i]) != null) {
            continue;
        }
        if (A[i] > max) {
            max = A[i];
        }
        uniqueNumbers.put(A[i], true);
        sum += A[i];
    }
    int completeSum = (max * (max + 1)) /  2;
    for(int j = 1; j <= Math.min((completeSum - sum), max); j++) {
        if(uniqueNumbers.get(j) == null) { //O(1)
            return j;
        }
    }
    //All negative case
    if(uniqueNumbers.isEmpty()) {
        return 1;
    }
    return 0;
}

Comme Stephen C l'a intelligemment souligné, la réponse doit être un nombre inférieur à la longueur du tableau. Je trouverais alors la réponse par recherche binaire. Cela optimise le pire des cas (de sorte que l'intervieweur ne peut pas vous attraper dans un scénario pathologique «et si»). Dans une interview, indiquez que vous faites cela pour optimiser le pire des cas.

La façon d'utiliser la recherche binaire est de soustraire le nombre que vous recherchez de chaque élément du tableau et de vérifier les résultats négatifs.

J'aime l'approche "suppose zéro". Si les nombres étaient aléatoires, zéro est hautement probable. Si «l'examinateur» a défini une liste non aléatoire, ajoutez-en une et devinez à nouveau:

LowNum=0
i=0
do forever {
  if i == N then leave /* Processed entire array */
  if array[i] == LowNum {
     LowNum++
     i=0
     }
   else {
     i++
   }
}
display LowNum

Le pire des cas est n * N avec n = N, mais en pratique n est très probablement un petit nombre (par exemple 1)

Je ne sais pas si j'ai bien compris la question. Mais si pour la liste 1,2,3,5,6 et que le nombre manquant est 4, alors le nombre manquant peut être trouvé dans O (n) par: (n + 2) (n + 1) / 2- (n + 1) n / 2

EDIT: désolé, je suppose que je pensais trop vite la nuit dernière. Quoi qu'il en soit, la deuxième partie devrait en fait être remplacée par sum (list), qui est là où O (n) vient. La formule révèle l'idée derrière elle: pour n entiers séquentiels, la somme doit être (n + 1) * n / 2. S'il manque un nombre, la somme sera égale à la somme de (n + 1) entiers séquentiels moins le nombre manquant.

Merci d'avoir souligné le fait que je mettais quelques pièces du milieu dans mon esprit.

Bravo aux fourmis Aasma! J'ai réfléchi à la réponse pendant environ 15 minutes et je suis parvenu indépendamment à une réponse dans la même veine que la vôtre:

#define SWAP(x,y) { numerictype_t tmp = x; x = y; y = tmp; }
int minNonNegativeNotInArr (numerictype_t * a, size_t n) {
    int m = n;
    for (int i = 0; i < m;) {
        if (a[i] >= m || a[i] < i || a[i] == a[a[i]]) {
            m--;
            SWAP (a[i], a[m]);
            continue;
        }
        if (a[i] > i) {
            SWAP (a[i], a[a[i]]);
            continue;
        }
        i++;
    }
    return m;
}

m représente "la sortie maximale possible actuelle étant donné ce que je sais des i premières entrées et en supposant rien d'autre sur les valeurs jusqu'à l'entrée à m-1".

Cette valeur de m ne sera retournée que si (a [i], ..., a [m-1]) est une permutation des valeurs (i, ..., m-1). Ainsi, si a [i]> = m ou si a [i] <i ou si a [i] == a [a [i]] nous savons que m est la mauvaise sortie et doit être au moins un élément plus bas. Donc, en décrémentant m et en échangeant un [i] avec le a [m], nous pouvons récurer.

Si ce n'est pas vrai mais a [i]> i alors sachant que a [i]! = A [a [i]] nous savons que permuter a [i] avec a [a [i]] augmentera le nombre d'éléments à leur place.

Sinon a [i] doit être égal à i auquel cas on peut incrémenter i sachant que toutes les valeurs jusqu'à et y compris cet indice sont égales à leur indice.

La preuve que cela ne peut pas entrer dans une boucle infinie est laissée comme exercice au lecteur. :)

Le fragment Dafny de la réponse d'Ants montre pourquoi l'algorithme en place peut échouer. La requirespré-condition décrit que les valeurs de chaque élément ne doivent pas dépasser les limites du tableau.

method AntsAasma(A: array<int>) returns (M: int)
  requires A != null && forall N :: 0 <= N < A.Length ==> 0 <= A[N] < A.Length;
  modifies A; 
{
  // Pass 1, move every value to the position of its value
  var N := A.Length;
  var cursor := 0;
  while (cursor < N)
  {
    var target := A[cursor];
    while (0 <= target < N && target != A[target])
    {
        var new_target := A[target];
        A[target] := target;
        target := new_target;
    }
    cursor := cursor + 1;
  }

  // Pass 2, find first location where the index doesn't match the value
  cursor := 0;
  while (cursor < N)
  {
    if (A[cursor] != cursor)
    {
      return cursor;
    }
    cursor := cursor + 1;
  }
  return N;
}

Collez le code dans le validateur avec et sans la forall ...clause pour voir l'erreur de vérification. La deuxième erreur est due au fait que le vérificateur ne peut pas établir une condition de fin pour la boucle Pass 1. Cela revient à quelqu'un qui comprend mieux l'outil.

Voici une réponse en Java qui ne modifie pas l'entrée et utilise le temps O (N) et N bits plus une petite surcharge constante de mémoire (où N est la taille de la liste):

int smallestMissingValue(List<Integer> values) {
    BitSet bitset = new BitSet(values.size() + 1);
    for (int i : values) {
        if (i >= 0 && i <= values.size()) {
            bitset.set(i);
        }
    }
    return bitset.nextClearBit(0);
}

def solution(A):

index = 0
target = []
A = [x for x in A if x >=0]

if len(A) ==0:
    return 1

maxi = max(A)
if maxi <= len(A):
    maxi = len(A)

target = ['X' for x in range(maxi+1)]
for number in A:
    target[number]= number

count = 1
while count < maxi+1:
    if target[count] == 'X':
        return count
    count +=1
return target[count-1] + 1

Obtenu 100% pour la solution ci-dessus.

1) Filtre négatif et zéro

2) Trier / distinguer

3) Visitez le tableau

Complexité : O (N) ou O (N * log (N))

en utilisant Java8

public int solution(int[] A) {
            int result = 1;
    boolean found = false;
    A = Arrays.stream(A).filter(x -> x > 0).sorted().distinct().toArray();
    //System.out.println(Arrays.toString(A));
    for (int i = 0; i < A.length; i++) {
        result = i + 1;
        if (result != A[i]) {
            found = true;
            break;
        }
    }
    if (!found && result == A.length) {
        //result is larger than max element in array
        result++;
    }
    return result;
}

Un unordered_set peut être utilisé pour stocker tous les nombres positifs, puis nous pouvons itérer de 1 à la longueur de unordered_set, et voir le premier nombre qui ne se produit pas.

int firstMissingPositive(vector<int>& nums) {

    unordered_set<int> fre;
    // storing each positive number in a hash.
    for(int i = 0; i < nums.size(); i +=1)
    {
        if(nums[i] > 0)
            fre.insert(nums[i]);
     }

    int i = 1;
    // Iterating from 1 to size of the set and checking 
    // for the occurrence of 'i'

    for(auto it = fre.begin(); it != fre.end(); ++it)
    {
        if(fre.find(i) == fre.end())
            return i;
        i +=1;
    }

    return i;
}

Solution via javascript de base

var a = [1, 3, 6, 4, 1, 2];

function findSmallest(a) {
var m = 0;
  for(i=1;i<=a.length;i++) {
    j=0;m=1;
    while(j < a.length) {
      if(i === a[j]) {
        m++;
      }
      j++;
    }
    if(m === 1) {
      return i;
    }
  }
}

console.log(findSmallest(a))

J'espère que cela aide quelqu'un.

Avec python ce n'est pas le plus efficace, mais correct

#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
import datetime

# write your code in Python 3.6

def solution(A):
    MIN = 0
    MAX = 1000000
    possible_results = range(MIN, MAX)

    for i in possible_results:
        next_value = (i + 1)
        if next_value not in A:
            return next_value
    return 1

test_case_0 = [2, 2, 2]
test_case_1 = [1, 3, 44, 55, 6, 0, 3, 8]
test_case_2 = [-1, -22]
test_case_3 = [x for x in range(-10000, 10000)]
test_case_4 = [x for x in range(0, 100)] + [x for x in range(102, 200)]
test_case_5 = [4, 5, 6]
print("---")
a = datetime.datetime.now()
print(solution(test_case_0))
print(solution(test_case_1))
print(solution(test_case_2))
print(solution(test_case_3))
print(solution(test_case_4))
print(solution(test_case_5))

def solution(A):
    A.sort()
    j = 1
    for i, elem in enumerate(A):
        if j < elem:
            break
        elif j == elem:
            j += 1
            continue
        else:
            continue
    return j

cela peut aider:

0- A is [5, 3, 2, 7];
1- Define B With Length = A.Length;                            (O(1))
2- initialize B Cells With 1;                                  (O(n))
3- For Each Item In A:
        if (B.Length <= item) then B[Item] = -1                (O(n))
4- The answer is smallest index in B such that B[index] != -1  (O(n))