Problème
La liste contient n nombres distincts choisis parmi 0, 1, …, n, donc exactement un nombre de cet intervalle est absent. Trouvez-le. (Indice : comparez la somme attendue avec la somme réelle.)
Implémentez missing_number(numbers).
Entrée
numbers : n nombres distincts de 0 à n.
Sortie
Retournez le nombre manquant.
Contraintes
0 ≤ n ≤ 100 000
Exemples
Entrée :
numbers = [3, 0, 1]
Sortie attendue :
expected = 2Entrée :
std::vector<long long> numbers = {3, 0, 1};
Sortie attendue :
long long expected = 2;Entrée :
long[] numbers = new long[] {3, 0, 1};
Sortie attendue :
long expected = 2;Explication
n = 3, donc l'intervalle est 0–3 ; 2 est manquant.
Entrée :
numbers = [0]
Sortie attendue :
expected = 1Entrée :
std::vector<long long> numbers = {0};
Sortie attendue :
long long expected = 1;Entrée :
long[] numbers = new long[] {0};
Sortie attendue :
long expected = 1;Explication
n = 1 et l'intervalle est 0–1 ; 1 est manquant.
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Les nombres doivent couvrir toute la plage de 0 à n, sauf un trou.
Indice 2
Comparez le total qu’aurait la plage complète avec ce que la liste totalise réellement.
Indice 3
Faites attention au cas où la valeur manquante est 0 ou n.
Complexité attendue
temps O(n), espace supplémentaire O(1)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.