Méditations LeetCode : numéro manquant

Commençons par la description de ce problème :

Étant donné un tableau nums contenant n nombres distincts dans la plage [0, n], renvoie le seul nombre de la plage qui manque dans le tableau.

Par exemple :

Input: nums = [3, 0, 1]
Output: 2

Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0, 3]. 2 is the missing number in the range since it does not appear in nums.

Ou :

Input: nums = [0, 1]
Output: 2

Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0, 2]. 2 is the missing number in the range since it does not appear in nums.

Ou :

Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8

Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0, 9]. 8 is the missing number in the range since it does not appear in nums.

Il est également indiqué que tous les nombres de chiffres sont uniques.

---

Un moyen simple de résoudre ce problème consiste à obtenir la somme totale de la plage, puis à soustraire la somme du tableau donné. Ce qui restera sera le numéro manquant.

Cela peut être fait en utilisant réduire pour additionner les nombres, comme ceci :

function missingNumber(nums: number[]): number {
  return Array.from({ 
    length: nums.length + 1 
  }, (_, idx) => idx).reduce((acc, item) => acc + item, 0) 
  - nums.reduce((acc, item) => acc + item, 0);
}

Tout d'abord, nous créons un tableau avec des valeurs de 0 à nums.length 1 et obtenons sa somme, puis soustrayons-en la somme des nombres.

Cependant, les complexités temporelles et spatiales seront $O(n)$O(n) avec cette solution pendant que nous créons un tableau pour la gamme.

Nous pouvons avoir une solution plus (en termes de stockage) efficace en utilisant la manipulation des bits.
En fait, nous pouvons utiliser une opération XOR pour nous aider.

Pour rappel, XOR donne 1 si les deux bits sont différents, c'est-à-dire que l'un d'eux est 0 et l'autre est 1.
Lorsque nous XOR un nombre avec lui-même, le résultat sera 0, car tous les bits sont identiques.

Par exemple, 3 en binaire vaut 11, quand on fait 11 ^ 11 le résultat est 0 :

const n = 3;
const result = n ^ n; // 0

En d'autres termes, une opération XOR d'un nombre avec lui-même donnera 0.

Si nous effectuons XOR avec chaque nombre du tableau avec les indices, ils finiront tous par s'annuler (résultat en 0), ne laissant que le nombre manquant.

On pourrait penser que tous les nombres ne sont pas à leur index, par exemple si nums vaut [3, 0, 1], il est évident que 3 n'a même pas d'"index 3" qui puisse lui être associé !

Pour cela, nous pouvons commencer par initialiser notre résultat à nums.length. Maintenant, même si le nombre manquant est égal à nums.length, nous traitons ce cas limite.

let result = nums.length;

De plus, XOR est commutatif et associatif, il n'est donc pas important à quel index un nombre apparaît (ou n'en a pas, comme dans l'exemple ci-dessus) - ils finiront par s'annuler.

Maintenant, avec une boucle for, nous pouvons faire le XOR en utilisant l'opérateur d'affectation XOR au niveau du bit :

for (let i = 0; i < nums.length; i++) {
  result ^= i ^ nums[i];
}

Et le résultat final est le numéro manquant. La solution globale ressemble à ceci :

Input: nums = [3, 0, 1]
Output: 2

Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0, 3]. 2 is the missing number in the range since it does not appear in nums.

Complexité temporelle et spatiale

La complexité temporelle est à nouveau $O(n)$O(n) au fur et à mesure que nous parcourons chaque nombre du tableau, mais la complexité spatiale sera $O(1)$O(1) car nous n'avons aucun besoin de stockage supplémentaire qui augmentera à mesure que la taille d'entrée augmente.

---

Ensuite, nous examinerons le dernier problème de toute la série, Somme de deux entiers. En attendant, bon codage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!