Product of Array Except Self

Q: Pourquoi la division n’est-elle pas autorisée dans le produit du tableau sauf soi-même ?

Diviser le produit total par nums[i] ne fonctionne pas lorsque le tableau contient un zéro, car le produit total vaut 0 et il faudrait diviser par 0 à l’indice du zéro lui-même. Pour que cela fonctionne, il faut compter les zéros et gérer des cas particuliers. Cette règle vous oriente vers les produits préfixes et suffixes, qui gèrent les zéros sans aucun cas particulier.

MoyenSommes préfixes

+10

Vous recevez un tableau d’entiers nums. Renvoyez un tableau answer de même longueur, où answer[i] est le produit de tous les éléments de nums, sauf celui à l’indice i. Faites-le en O(n) et sans utiliser la division.

Fonction

productExceptSelf(nums: integer-array) → integer-array

numsinteger-array: le tableau d’entiers, comportant au moins deux éléments
Renvoieinteger-array: un tableau dont la valeur à l’indice i est le produit de tous les éléments sauf nums[i]

Contraintes

2 ≤ nums.length ≤ 10⁴
-30 ≤ nums[i] ≤ 30
Le produit de toutes les valeurs non nulles dans nums tient dans un entier signé de 32 bits, donc chaque produit que tu calcules en cours de route tient également.

Exemples

Entrée: nums = [2, 3, 4, 5]
Sortie: [60, 40, 30, 24]
Explication: En omettant le 2, il reste 3 × 4 × 5 = 60, et en omettant le 5, il reste 2 × 3 × 4 = 24. Les deux nombres du milieu fonctionnent de la même manière : 2 × 4 × 5 = 40 et 2 × 3 × 5 = 30.

+14 tests cachés à la soumission

Pour aller plus loin

Peux-tu utiliser uniquement O(1) espace supplémentaire, sans compter le tableau que tu renvoies ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Le produit de toutes les valeurs sauf nums[i] est le produit des valeurs à sa gauche multiplié par le produit des valeurs à sa droite. Diviser le produit total par nums[i] semble plus court, mais ce n’est pas autorisé ici et cela échoue avec les zéros, pour lesquels le produit total vaut 0. Les produits préfixes et suffixes permettent d’obtenir tous les produits à gauche et à droite en deux parcours, ce qui donne une complexité temporelle de O(n). Le tableau de sortie peut contenir les produits à gauche, et une variable transporte le produit à droite : aucun autre tableau n’est nécessaire.

Multipliez les autres pour chaque indice

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Suivez la définition. Pour chaque indice i, initialisez un produit à 1 et multipliez-le par chaque nums[j] dont l’indice j est différent de i. Ignorer cet indice, plutôt que de le diviser ensuite, permet de gérer les zéros sans problème : dans [-2, 5, 0, 3], le produit pour l’indice 2 ne tient jamais compte du 0 et vaut -30.

C’est correct, mais cela répète du travail. Les produits pour l’indice 0 et l’indice 1 partagent toutes les valeurs sauf deux, et vous les multipliez quand même toutes à nouveau. Chacune des n positions nécessite n-1 multiplications, soit environ 10^8 au total lorsque n = 10^4. C exécute cela en une fraction de seconde, mais Python, Ruby ou R mettent bien trop longtemps.

Algorithme

Crée un tableau de réponses de longueur n.
Pour chaque indice i, définis product sur 1.
Multiplie product par chaque nums[j] dont l’indice j est différent de i.
Stocke product à l’indice i du tableau de réponses.
Retourne le tableau de réponses.

def productExceptSelf(nums):
    n = len(nums)
    answer = []
    for i in range(n):
        product = 1
        for j in range(n):
            if j != i:
                product *= nums[j]
        answer.append(product)
    return answer

Tableaux des produits préfixes et suffixes

Intuition

Séparez le produit pour l’indice i en deux : les valeurs avant i et les valeurs après. Appelez ces produits before[i] et after[i]. Alors answer[i] = before[i] × after[i], et nums[i] est exclu sans aucune division.

Chaque tableau se construit à partir de son voisin avec une multiplication. before[0] vaut 1, le produit d’aucune valeur, et before[i] = before[i-1] × nums[i-1]. À partir de l’autre extrémité, after[n-1] vaut 1 et after[i] = after[i+1] × nums[i+1]. Pour [2, 3, 4, 5], on obtient before = [1, 2, 6, 24] et after = [60, 20, 5, 1], et leur multiplication position par position donne [60, 40, 30, 24].

Trois parcours de n étapes donnent un temps en O(n). Les deux tableaux auxiliaires nécessitent O(n) mémoire supplémentaire, que l’approche suivante élimine.

Algorithme

Remplis before en partant de la gauche : before[0] = 1, puis chaque entrée est égale à l’entrée précédente multipliée par la valeur précédente.
Remplis after en partant de la droite : after[n-1] = 1, puis chaque entrée est égale à l’entrée suivante multipliée par la valeur suivante.
Définis answer[i] comme étant égal à before[i] × after[i] pour chaque indice.
Renvoie answer.

def productExceptSelf(nums):
    n = len(nums)
    # before[i] = product of nums[0..i-1], after[i] = product of nums[i+1..n-1]
    before = [1] * n
    after = [1] * n
    for i in range(1, n):
        before[i] = before[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1):
        after[i] = after[i + 1] * nums[i + 1]
    return [before[i] * after[i] for i in range(n)]

Produits gauches dans la réponse, un produit droit en cours d’exécution

Intuition

Tu n’as jamais besoin de tout le tableau after en même temps. En parcourant le tableau depuis la droite, le produit des valeurs à droite de i est un seul nombre. Garde-le dans une variable right et mets-le à jour avec une multiplication à chaque étape.

Écris donc directement les produits de gauche dans le tableau de réponse lors d’un premier passage. Lors d’un second passage depuis la droite, multiplie answer[i] par right, puis multiplie seulement ensuite right par nums[i]. L’ordre compte : quand tu utilises right à l’indice i, il ne doit pas encore inclure nums[i].

Pour [2, 3, 4, 5], le premier passage donne [1, 2, 6, 24]. Le second passage utilise right = 1, 5, 20, 60 aux indices 3, 2, 1, 0 et transforme le tableau en [60, 40, 30, 24]. La complexité temporelle reste O(n) et, en plus du tableau que tu renvoies, la mémoire supplémentaire se limite à une variable : O(1).

Algorithme

Définis answer[0] = 1, puis, de gauche à droite, définis answer[i] = answer[i-1] × nums[i-1].
Définis right à 1.
En partant du dernier indice jusqu’à 0, multiplie answer[i] par right.
Multiplie ensuite right par nums[i].
Retourne answer.

def productExceptSelf(nums):
    n = len(nums)
    # Pass 1: answer[i] = product of everything left of i
    answer = [1] * n
    for i in range(1, n):
        answer[i] = answer[i - 1] * nums[i - 1]
    # Pass 2: multiply in the product of everything right of i
    right = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= right
        right *= nums[i]
    return answer

Pièges et cas limites

Les bogues ici viennent des zéros, de l’ordre des deux mises à jour lors du second passage et des limites du tableau.

Diviser le produit total par nums[i] échoue dès qu’un 0 apparaît. Pour [-2, 5, 0, 3], le total vaut 0 et, à l’indice 2, il faudrait calculer 0 divisé par 0. Compter les zéros peut résoudre le problème, mais l’énoncé interdit de toute façon la division.
Multiplier right par nums[i] avant de l’utiliser inclut nums[i] dans son propre produit. Pour [2, 3, 4, 5], la dernière valeur devient 120 au lieu de 24.
Commencer les produits de gauche à nums[0] au lieu de 1. Rien ne se trouve à gauche de l’indice 0 : son produit à gauche est donc le produit vide, 1, et answer[0] finit par être uniquement le produit des valeurs à sa droite.
Bornes des boucles : le passage de gauche lit nums[i-1], il commence donc à l’indice 1. Un tableau des suffixes lit nums[i+1], il commence donc à l’indice n-2.
Deux zéros rendent toutes les réponses égales à 0. Un seul zéro rend toutes les réponses égales à 0, sauf celle à l’indice du zéro. Teste les deux cas avant de faire confiance à ton code.

Questions fréquentes4

Quelle est la complexité temporelle de « Product of Array Except Self » ?

La solution par préfixes et suffixes s’exécute en temps O(n) : un parcours de gauche à droite et un de droite à gauche. En stockant les produits à gauche dans le tableau de sortie et en conservant un seul produit courant à droite, elle nécessite O(1) d’espace supplémentaire en plus du tableau de sortie. Multiplier toutes les autres valeurs pour chaque indice prend un temps O(n²).

Pourquoi la division n’est-elle pas autorisée dans le produit du tableau sauf soi-même ?

Diviser le produit total par nums[i] ne fonctionne pas lorsque le tableau contient un zéro, car le produit total vaut 0 et il faudrait diviser par 0 à l’indice du zéro lui-même. Pour que cela fonctionne, il faut compter les zéros et gérer des cas particuliers. Cette règle vous oriente vers les produits préfixes et suffixes, qui gèrent les zéros sans aucun cas particulier.

Le tableau de sortie est-il comptabilisé comme espace supplémentaire ?

Non. Tu dois quand même renvoyer la réponse, donc la convention habituelle ne la compte pas dans l’espace utilisé. Y stocker les produits de gauche et conserver le produit de droite dans une variable compte donc comme un espace supplémentaire en O(1).

Comment Product of Array Except Self gère-t-il les zéros ?

Avec les produits préfixes et suffixes, les zéros ne nécessitent aucun cas particulier. Tout produit à gauche ou à droite qui dépasse un zéro vaut 0, et le produit à l’indice du zéro lui-même l’ignore. Avec deux zéros ou plus, chaque produit en contient un, donc toutes les réponses valent 0.

Python

def productExceptSelf(nums):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [2, 3, 4, 5]

Attendu

[60, 40, 30, 24]

Product of Array Except Self

Fonction

Contraintes

Exemples

Indices

Solution

Multipliez les autres pour chaque indice

Tableaux des produits préfixes et suffixes

Produits gauches dans la réponse, un produit droit en cours d’exécution

Pièges et cas limites

Questions fréquentes4

Problèmes similaires