Product of Array Except Self
Étant donné un tableau d'entiers, renvoyer un tableau tel que chaque case du tableau soit le produit de tous les éléments du tableau initial, excepté celui à l'indice concercné
LEETCODE
Antoine Latgrand NDIAYE
1/18/20252 min read
Description
[EN]
Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i]. Each product is guaranteed to fit in a 32-bit integer.
Constraints:
2 <= nums.length <= 1000
-20 <= nums[i] <= 20
[FR]
Étant donné un tableau d'entiers nums, retournez un tableau output où output[i] est le produit de tous les éléments de nums sauf nums[i]. Il est garanti que chaque produit tient dans un entier 32 bits.
Contraintes :
2 <= nums.length <= 1000 : Le tableau nums contient entre 2 et 1000 éléments.
-20 <= nums[i] <= 20 : Chaque élément de nums est compris entre -20 et 20.
Approche 1: Utilisation d'un tableau copie
On crée une copie du tableau nums
On itère sur notre tableau nums
On utilise une variable product représentant le produit pour la case actuelle
On itère sur notre copie
si l'indice concerné est le même que la case pour laquelle on est en train de calculer, on le saute (if j == i)
sinon, on multiplie notre produit par la valeur actuelle
on remplace al valeur de notre tableau initiale par la valeur du produit calculé
A la fin du parcours, on a trouvé notre solution et on renvoie notre nouveau tableau avec les produits demandés
Complexité temporelle: O(n²) car on effectue une double parcours
Complexité spatiale: O(n) car utilisation d'un tableau copie
Une première solution intuitive consiste à créer une copie du tableau et à l'utiliser pour calculer les produits.
Approche 2: Utilisation de tableaux prefixe et postfixe
Deux tableaux, prefix et postfix, sont créés pour stocker respectivement les produits cumulatifs des éléments avant et après chaque élément.
Tous les éléments de prefix et postfix sont initialisés à 1, car le produit neutre est 1.
Un produit cumulé, product, est utilisé pour calculer le produit des éléments avant chaque indice dans nums.
De manière similaire, un produit cumulé est utilisé pour calculer les produits des éléments après chaque indice dans nums. Cette fois, on parcourt le tableau dans l'ordre inverse.
Le produit de chaque élément sauf lui-même est obtenu en multipliant les valeurs correspondantes dans prefix et postfix.
Complexité temporelle: O(n) car on effectue que des parcours linéaires
Complexité spatiale: O(n) car utilisation de tableau prefix et postfix
Une solution optimisée consiste à utiliser des tableau postfixe et prefixe pour la résolution: