Product of Array Except Self

Q: ¿Por qué no se permite la división en «Producto de la matriz excepto a sí misma»?

Dividir el producto total por nums[i] falla cuando el arreglo contiene un cero, porque el total es 0 y el índice del propio cero requeriría una división por 0. Para que funcione, se necesita contar los ceros y manejar casos especiales. La regla te lleva a usar productos de prefijos y sufijos, que manejan los ceros sin ningún caso especial.

MedioSuma de prefijos

+10

Se te proporciona un array de enteros nums. Devuelve un array answer de la misma longitud, donde answer[i] es el producto de todos los elementos de nums excepto el que está en el índice i. Hazlo en tiempo O(n) y sin usar la división.

Función

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

numsinteger-array: el arreglo de números enteros, con al menos dos elementos
Devuelveinteger-array: un array cuyo valor en el índice i es el producto de todos los elementos excepto nums[i]

Restricciones

2 ≤ nums.length ≤ 10⁴
-30 ≤ nums[i] ≤ 30
El producto de todos los valores distintos de cero de nums cabe en un entero con signo de 32 bits, así que todos los productos que calcules por el camino también caben.

Ejemplos

Entrada: nums = [2, 3, 4, 5]
Salida: [60, 40, 30, 24]
Explicación: Al omitir el 2, queda 3 × 4 × 5 = 60, y al omitir el 5, queda 2 × 3 × 4 = 24. Los dos del medio funcionan de la misma manera: 2 × 4 × 5 = 40 y 2 × 3 × 5 = 30.

+14 pruebas ocultas al enviar

Para ir más allá

¿Puedes usar solo espacio adicional O(1), sin contar el arreglo que devuelves?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

El producto de todo excepto nums[i] es el producto de los valores a su izquierda multiplicado por el producto de los valores a su derecha. Dividir el producto total por nums[i] parece más corto, pero aquí no está permitido y falla con los ceros, cuando el total es 0. Los productos de prefijos y sufijos proporcionan todos los productos de la izquierda y de la derecha en dos pasadas, así que la respuesta requiere O(n) de tiempo. El arreglo de salida puede contener los productos de la izquierda, y una variable lleva el producto de la derecha, por lo que no se necesita ningún otro arreglo.

Multiplica los demás para cada índice

Correcto, pero no termina con las pruebas más grandes

Intuición

Sigue la definición. Para cada índice i, inicia un producto en 1 y multiplica todos los nums[j] cuyo índice j no sea i. Omitir ese índice, en lugar de dividirlo después, hace que los ceros no causen problemas: en [-2, 5, 0, 3], el producto para el índice 2 nunca incluye el 0 y da -30.

Es correcto, pero repite trabajo. Los productos para el índice 0 y el índice 1 comparten todos los valores excepto dos, y aun así vuelves a multiplicarlos todos. Cada una de las n posiciones requiere n-1 multiplicaciones, unas 10^8 en total cuando n = 10^4. C puede hacerlo en una fracción de segundo, pero Python, Ruby o R tardan demasiado.

Algoritmo

Crea un array de respuestas de longitud n.
Para cada índice i, establece product en 1.
Multiplica product por cada nums[j] cuyo índice j no sea i.
Almacena product en el índice i de la respuesta.
Devuelve la respuesta.

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

Arreglos de productos de prefijos y sufijos

Intuición

Divide el producto para el índice i en dos: los valores anteriores a i y los valores posteriores. Llama a esos productos before[i] y after[i]. Después, answer[i] = before[i] × after[i], y se omite nums[i] sin hacer ninguna división.

Cada array se construye a partir del elemento vecino con una multiplicación. before[0] es 1, el producto de ningún valor, y before[i] = before[i-1] × nums[i-1]. Desde el otro extremo, after[n-1] es 1 y after[i] = after[i+1] × nums[i+1]. Para [2, 3, 4, 5] obtienes before = [1, 2, 6, 24] y after = [60, 20, 5, 1], y al multiplicarlos posición por posición se obtiene [60, 40, 30, 24].

Tres recorridos de n pasos requieren un tiempo O(n). Los dos arrays auxiliares cuestan O(n) de memoria adicional, que el siguiente enfoque elimina.

Algoritmo

Rellena before desde la izquierda: before[0] = 1, después cada elemento es el elemento anterior multiplicado por el valor anterior.
Rellena after desde la derecha: after[n-1] = 1, después cada elemento es el elemento siguiente multiplicado por el valor siguiente.
Asigna before[i] × after[i] a answer[i] para cada índice.
Devuelve 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)]

Productos izquierdos en la respuesta, un producto derecho en ejecución

Intuición

Nunca necesitas tener todo el arreglo after a la vez. Al recorrerlo desde el extremo derecho, el producto de los valores a la derecha de i es un solo número. Guárdalo en una variable right y actualízala con una multiplicación por paso.

Así que escribe directamente los productos de la izquierda en el arreglo de respuesta en una primera pasada. En una segunda pasada desde la derecha, multiplica answer[i] por right y solo entonces multiplica right por nums[i]. El orden importa: cuando uses right en el índice i, todavía no debe incluir nums[i].

Para [2, 3, 4, 5], la primera pasada deja [1, 2, 6, 24]. La segunda pasada usa right = 1, 5, 20, 60 en los índices 3, 2, 1, 0 y transforma el arreglo en [60, 40, 30, 24]. El tiempo sigue siendo O(n) y, además del arreglo que devuelves, la memoria adicional es una variable: O(1).

Algoritmo

Establece answer[0] = 1 y después, de izquierda a derecha, establece answer[i] = answer[i-1] × nums[i-1].
Establece right en 1.
Desde el último índice hasta 0, multiplica answer[i] por right.
Después, multiplica right por nums[i].
Devuelve 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

Errores comunes y casos límite

Los errores aquí se deben a los ceros, al orden de las dos actualizaciones en la segunda pasada y a los extremos del arreglo.

Dividir el producto total entre nums[i] falla cuando aparece un 0. Para [-2, 5, 0, 3], el total es 0, y el índice 2 necesitaría dividir 0 entre 0. Contar los ceros puede solucionarlo, pero el problema prohíbe la división de todos modos.
Multiplicar right por nums[i] antes de usarlo incluye nums[i] en su propio producto. Para [2, 3, 4, 5], el último valor pasa a ser 120 en lugar de 24.
Empezar los productos de la izquierda en nums[0] en vez de 1. No hay nada a la izquierda del índice 0, así que su producto izquierdo es el producto vacío, 1, y answer[0] termina siendo únicamente el producto de los valores que están a su derecha.
Límites de los bucles: la pasada hacia la izquierda lee nums[i-1], así que empieza en el índice 1. Un arreglo de sufijos lee nums[i+1], así que empieza en n-2.
Dos ceros hacen que todas las respuestas sean 0. Un cero hace que todas las respuestas sean 0, excepto la del índice del propio cero. Prueba ambos casos antes de confiar en tu código.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Product of Array Except Self?

La solución con prefijos y sufijos se ejecuta en tiempo O(n): una pasada de izquierda a derecha y otra de derecha a izquierda. Con los productos de la izquierda almacenados en el array de salida y un único producto acumulado de la derecha, necesita O(1) de espacio adicional, aparte del espacio de salida. Multiplicar todos los demás valores para cada índice requiere un tiempo O(n²).

¿Por qué no se permite la división en «Producto de la matriz excepto a sí misma»?

Dividir el producto total por nums[i] falla cuando el arreglo contiene un cero, porque el total es 0 y el índice del propio cero requeriría una división por 0. Para que funcione, se necesita contar los ceros y manejar casos especiales. La regla te lleva a usar productos de prefijos y sufijos, que manejan los ceros sin ningún caso especial.

¿La matriz de salida cuenta como espacio adicional?

No. Tienes que devolver la respuesta de todos modos, así que la convención habitual no lo incluye en el recuento de espacio. Por lo tanto, almacenar en él los productos de la izquierda y mantener el producto de la derecha en una variable cuenta como espacio adicional O(1).

¿Cómo maneja Product of Array Except Self los ceros?

Con los productos de prefijo y sufijo, los ceros no requieren ningún caso especial. Cualquier producto por la izquierda o por la derecha que pase de un cero es 0, y el producto del índice del propio cero lo omite. Con dos o más ceros, todos los productos contienen uno, así que todas las respuestas son 0.

Python

def productExceptSelf(nums):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

nums = [2, 3, 4, 5]

Esperado

[60, 40, 30, 24]

Product of Array Except Self

Función

Restricciones

Ejemplos

Pistas

Solución

Multiplica los demás para cada índice

Arreglos de productos de prefijos y sufijos

Productos izquierdos en la respuesta, un producto derecho en ejecución

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares