Un peu de magie algorithmique ancienne, ou résoudre une séquence de tâches intrigante à partir de LeetCode

Il y a quelque temps, je suis tombé sur une série de tâches amusantes sur le site leetcode.com. Les tâches elles-mêmes ne sont pas trop difficiles, mais leurs solutions sont plutôt intrigantes. De plus, des problèmes de ce type apparaissent souvent lors des entretiens dans les grandes entreprises, et comprendre les méthodes de leur solution peut être très bénéfique.

La première tâche est 136. Numéro unique (facile)

Étant donné un tableau d'entiers non vide où chaque élément apparaît deux fois sauf un, vous devez trouver l'élément sans paire. Résolvez le problème en complexité temporelle O(n) et avec une mémoire supplémentaire constante.

Exemple 1:

Entrée : nombres = [1, 3, 3, 2, 6, 2, 1]

Sortie : 6

Exemple 2 :

Entrée : nombres = [12, 1, 1, 7, 1, 12, 1]

Sortie : 7

Exemple 3 :

Entrée : numéros = [6]

Sortie : 6

Nous exploiterons la propriété de la fonction XOR, qui donne 1 uniquement lorsque ses opérandes sont différents. En parcourant tous les éléments du tableau et en effectuant un XOR au niveau du bit sur eux, nous mettrons à zéro toutes les valeurs de bits identiques. En conséquence, ce qui restera sera le résultat souhaité.

Voici un court code de solution Python3 :

 def single_number(nums: list) -> int: result = 0 for el in nums: result ^= el return result

Nous utilisons uniquement autant de mémoire supplémentaire qu'un entier occupe et trouvons la solution en un seul passage dans le tableau donné, ce qui nous donne une complexité O(n). C'est une solution concise et élégante.

Le deuxième problème est 137. Numéro unique II (difficulté moyenne)

Étant donné un tableau d'entiers non vide où chaque élément apparaît trois fois sauf un, et un seul élément apparaît une fois, nous devons trouver cet élément unique. Résolvez le problème en complexité temporelle O(n) et avec une mémoire supplémentaire constante.

Exemple 1:

Entrée : nombres = [3, 1, 3, 3]

Sortie : 1

Exemple 2 :

Entrée : nombres = [12, 1, 1, 5, 1, 12, 12]

Sortie : 5

Exemple 3 :

Entrée : numéros = [6]

Sortie : 6

Malheureusement, nous ne pouvons pas utiliser l’astuce précédente dans ce cas puisque nous ne pouvons pas transformer les bits appariés à la position requise en zéros. Il serait tentant de transformer le tableau donné dans le format de la tâche précédente, puis de le résoudre de la même manière.

En raisonnant de cette façon, il est facile de remarquer que si nous savions que nous avons déjà rencontré le nombre N deux (ou trois fois) en parcourant le tableau, nous pourrions ajouter un XOR supplémentaire avec N à la somme que nous obtenons. Cela rendrait le XOR final avec ce nombre égal, le supprimant ainsi de la somme finale, et ce qui resterait serait notre réponse.

 def single_number_ii(nums: list) -> int: mem = {} result = 0 for el in nums: if not mem.get(el, False): mem[el] = 1 else: mem[el] += 1 if mem[el] == 2: result ^= el result ^= el return result

Malheureusement, cette solution nécessiterait un maximum de (len(nums)-1)/3 en termes de mémoire, ce qui ne peut pas être considéré comme une consommation constante, il faudra donc chercher une autre solution.

Essayons de changer notre approche.

Plus tôt, nous avons utilisé XOR (qui représente l'addition modulo 2). Si nous avions implémenté l’addition modulo 3, nous aurions facilement pu appliquer l’astuce de l’exemple précédent.

Si nous pouvons mettre un nombre dans la réponse la première fois que nous le rencontrons, le mettre dans l'accumulateur la deuxième fois et mettre à zéro la réponse et l'accumulateur la troisième fois, cela nous aiderait à résoudre le problème en un seul passage. la liste avec une consommation de mémoire supplémentaire exactement égale à deux nombres entiers, répondant aux exigences de la tâche.

Alors, appliquons un peu plus de magie au niveau du bit :

 def single_number_137_ii(nums: list) -> int: ans, acc = 0, 0 for n in nums: ans = ans ^ n & ~acc acc = acc ^ n & ~ans return ans

De cette façon, tous les nombres triples sont mis à zéro et il ne nous reste que le nombre qui n'apparaît qu'une seule fois.

La troisième tâche est 260. Numéro unique III (difficulté moyenne)

Étant donné un tableau d'entiers non vide où chaque élément apparaît deux fois, à l'exception de deux éléments qui n'apparaissent qu'une seule fois, nous devons trouver ces éléments uniques. Le but est de résoudre le problème en complexité temporelle O(n) et avec une mémoire supplémentaire constante, et l'ordre des éléments uniques n'a pas d'importance.

Exemple 1:

Entrée : nombres = [1, 2, 1, 3, 2, 5]

Sortie : [3, 5]

Exemple 2 :

Entrée : nombres = [1, -2]

Sortie : [-2, 1]

Évidemment, nous pouvons facilement éliminer tous les nombres appariés en utilisant l’opération XOR, comme nous l’avons fait pour résoudre la première tâche. La complexité de la tâche réside alors dans l'identification de l'un des nombres uniques, après quoi le second peut être facilement calculé en le XOR avec notre somme XOR.

Pour y parvenir, il nous suffit de trouver les bits différents entre ces nombres uniques. Ensuite, nous parcourons à nouveau le tableau, effectuant une sommation XOR et divisant les résultats en deux groupes - pour les nombres où ce bit est défini et pour ceux où il est 0. En conséquence, nous obtenons les éléments uniques souhaités.

 def single_number_260(nums: list) -> int: res1, res2 = 0, 0 glob_xor = 0 for n in nums: glob_xor ^= n diff_bit = glob_xor & ~(glob_xor - 1) for n in nums: if n & diff_bit: res1 ^= n else: res2 ^= n return [res1, res2]

Bien qu'il faille parcourir le tableau deux fois, la complexité reste O(n) et la consommation de mémoire n'est que de 2 entiers.

NB : Malgré le fait que int en Python n'est pas exactement le même que int dans d'autres langages, nous considérerons sa taille comme une constante