Single Number
Tu reçois une liste nums dans laquelle chaque valeur apparaît exactement deux fois, sauf une valeur qui n’apparaît qu’une seule fois. Retourne la valeur qui n’apparaît qu’une fois.
Fonction
- numsinteger-array
- une liste où chaque valeur apparaît deux fois, sauf une
- Renvoieinteger
- la valeur qui n’apparaît qu’une seule fois
Contraintes
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- Chaque valeur apparaît exactement deux fois, sauf une valeur qui n’apparaît qu’une seule fois.
Exemples
- Entrée
- nums = [8, 3, 8]
- Sortie
- 3
- Explication
- 8 apparaît deux fois et 3 apparaît une fois, donc la réponse est 3.
- Entrée
- nums = [5, -2, 7, 5, 7]
- Sortie
- -2
- Explication
- 5 et 7 apparaissent chacun deux fois, et -2 est la seule valeur qui apparaît une fois. Une réponse négative se trouve de la même manière qu’une réponse positive.
- Entrée
- nums = [42]
- Sortie
- 42
- Explication
- Une liste contenant une seule valeur n’a aucune paire, donc cette valeur est la réponse.
+13 tests cachés à la soumission
Pour aller plus loin
Et si chaque valeur apparaissait trois fois, sauf une seule ? XOR à lui seul ne permet plus d’annuler les triplets. Peux-tu quand même trouver la valeur unique en O(n) et avec O(1) mémoire supplémentaire ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Si chaque paire de valeurs égales pouvait disparaître, il ne resterait que la réponse. Existe-t-il une opération qui transforme deux nombres égaux en rien ?
XOR a les propriétés suivantes :
x ^ xvaut0etx ^ 0vautx. L’ordre n’a pas d’importance non plus : les deux copies d’une valeur n’ont pas besoin d’être côte à côte pour s’annuler.Conservez une variable qui commence à
0. Faites un XOR avec chaque valeur denums, puis renvoyez-la. Aucune map ni aucun tri n’est nécessaire.
Solution
Trouver la valeur qui n’a pas de partenaire est un problème de comptage, et une table de hachage compte chaque valeur en un seul passage. Le hic, c’est la mémoire : une table grandit avec la liste. XOR évite d’avoir à compter, car XOR-er une valeur avec elle-même donne 0. Faites un XOR de toute la liste et chaque paire s’annule, laissant la valeur unique en un seul passage avec une seule variable.
Compter chaque valeur en parcourant
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Prenez chaque valeur à tour de rôle et parcourez toute la liste pour compter le nombre de fois où elle apparaît. Une valeur appartenant à une paire compte pour 2. La valeur unique compte pour 1 : renvoyez donc la première valeur dont le compte est égal à 1.
C’est correct, car les comptes découlent directement de la définition de la réponse et ne nécessitent aucune mémoire supplémentaire au-delà d’un compteur.
C’est lent, car chacune des n valeurs déclenche un parcours complet de n valeurs. Lorsque la valeur unique se trouve à la fin d’une liste de 9,999, cela représente près de 10^8 comparaisons.
Algorithme
- Parcourez chaque valeur de
nums. - Parcourez toute la liste et comptez les valeurs qui lui sont égales.
- Si le compte est de 1, renvoyez cette valeur.
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0Compter avec une table de hachage
Intuition
Parcourir de nouveau la liste pour chaque valeur répète le travail. Compte plutôt toutes les valeurs en un seul passage : une table de hachage associant chaque valeur à son nombre d’occurrences, où chaque étape ajoute 1 au nombre d’occurrences de la valeur courante.
Pour [5, -2, 7, 5, 7], la table contient à la fin 5 → 2, -2 → 1, 7 → 2. Un second passage dans la table trouve l’entrée dont le nombre d’occurrences est 1, soit -2.
Chaque valeur nécessite une mise à jour de la table, donc le temps d’exécution est O(n). La table contient environ n/2 entrées, ce qui représente une mémoire supplémentaire de O(n). En C, qui ne possède pas de table intégrée, un tableau de compteurs indexés par value + 10^4 joue le même rôle, car les valeurs sont petites.
Algorithme
- Crée une map vide associant chaque valeur à son nombre d’occurrences.
- Pour chaque valeur de
nums, ajoute 1 à son nombre d’occurrences. - Parcours la map et renvoie la valeur dont le nombre d’occurrences est 1.
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0Appliquez XOR à toutes les valeurs
Intuition
XOR compare deux nombres bit à bit et définit un bit là où ils diffèrent. Il en découle trois faits : x ^ x = 0, x ^ 0 = x et l’ordre des opérations n’a pas d’importance.
Faites donc un XOR de toute la liste dans une variable initialisée à 0. Vous pouvez regrouper les opérations de sorte que chaque paire rencontre son double, et chaque paire devient 0. Il reste 0 ^ single, soit la valeur unique. Pour [8, 3, 8] : 0 ^ 8 = 8, puis 8 ^ 3 = 11, puis 11 ^ 8 = 3.
Les nombres négatifs fonctionnent aussi. XOR agit sur les bits de la représentation en complément à deux, et deux nombres négatifs égaux ont des bits identiques ; ils s’annulent donc comme n’importe quelle autre paire. La boucle lit chaque valeur une fois et conserve une seule variable : un temps de O(n) et une mémoire supplémentaire de O(1).
Algorithme
- Définissez
resultsur 0. - Pour chaque valeur de
nums, définissezresultsurresult ^ value. - Retournez
result.
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
Pièges et cas limites
La boucle XOR est courte, alors les erreurs se cachent dans le choix du point de départ et dans les solutions de remplacement auxquelles on a recours.
- Initialiser
resultànums[0], puis parcourir toutes les valeurs, y compris l’indice 0. La première valeur est alors soumise à XOR deux fois et s’annule. Commence à 0 ou ignore l’indice 0. - Trier et comparer les éléments voisins par paires, puis oublier que la valeur unique peut être le dernier élément. Dans
[1, 1, 2], aucune paire ne diffère, et la réponse est le 2 restant. - Utiliser
2 × sum(distinct values) - sum(nums). Le résultat est correct, mais l’ensemble des valeurs distinctes nécessite une mémoire deO(n), ce que la version avec XOR évite. - S’attendre à ce que XOR fonctionne pour d’autres nombres d’occurrences. Il annule les valeurs qui apparaissent un nombre pair de fois. Si une valeur apparaissait trois fois, une copie subsisterait et fausserait la réponse.
Questions fréquentes4
Quelle est la complexité temporelle de Single Number ?
La solution XOR s’exécute en O(n) et utilise O(1) d’espace supplémentaire, car elle lit chaque valeur une seule fois et conserve une variable. Une table de hachage prend également O(n) en temps, mais nécessite O(n) de mémoire. Compter chaque valeur en effectuant un nouveau balayage prend O(n²).
Pourquoi XOR résout-il le problème du nombre unique ?
Faire un XOR d’un nombre avec lui-même donne 0, faire un XOR avec 0 ne change rien, et l’ordre des opérations n’a pas d’importance. Ainsi, lorsque tu fais un XOR sur toute la liste, chaque paire peut être regroupée et s’annule pour donner 0. Seule la valeur sans partenaire reste.
Est-ce que l’astuce XOR fonctionne avec les nombres négatifs ?
Oui. XOR opère sur les bits qui stockent le nombre, et les nombres négatifs sont stockés en complément à deux. Deux nombres négatifs égaux ont des bits identiques, ils s’annulent donc exactement comme les nombres positifs. Dans [5, -2, 7, 5, 7], le résultat est -2.
Comment résoudre cela lorsque les autres valeurs apparaissent trois fois ?
XOR annule les paires, pas les triplets, donc il échoue dans ce cas. À la place, compte combien de valeurs ont chacun des 32 bits à 1. Pour chaque bit, ce compte modulo 3 correspond au bit de la valeur unique, car les triplets ajoutent des multiples de 3. Cela s’exécute toujours en temps O(n) avec une mémoire supplémentaire de O(1).
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
Python
def singleNumber(nums):
# Écrivez le code iciCas 1
Cas 2
Cas 3
Entrée
nums = [8, 3, 8]
Attendu
3