Cómo encontrar el producto de todos los elementos en una matriz excepto uno mismo - Blind 75 LeetCode

Descripción de la tarea:

Dada una matriz de enteros nums , devuelva una answer de matriz tal que answer[i] sea igual al producto de todos los elementos de nums excepto nums[i] .

Se garantiza que el producto de cualquier prefijo o sufijo de nums cabe en un número entero de 32 bits .

Debes escribir un algoritmo que se ejecute en tiempo O(n) y sin usar la operación de división.

Ejemplo 1:

 Input: nums = [1,2,3,4] Output: [24,12,8,6]

Ejemplo 2:

 Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]

Restricciones:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• Se garantiza que el producto de cualquier prefijo o sufijo de nums cabe en un número entero de 32 bits .

Seguimiento: ¿Puedes resolver el problema en la complejidad del espacio extra O(1) ? (La matriz de salida no cuenta como espacio adicional para el análisis de complejidad espacial).

Razonamiento:

Esta es una tarea algorítmica interesante. Para cada índice en la matriz dada, necesitamos encontrar un producto de todos los elementos de la matriz excepto el elemento en la posición actual. Consideremos el ejemplo dado:

Creo que al mirar los ejemplos anteriores, entendiste la idea principal. Una idea inmediata puede surgir en su cabeza, "multipliquemos todos los elementos en la matriz, y al tenerlo, podemos dividirlo por el elemento en cada posición, y nos dará el resultado correcto". Es la forma correcta de pensar y de hecho nos da el resultado correcto, pero el enunciado del problema dice que no podemos usar la operación de división.

Sigamos con la lluvia de ideas. Otra idea podría ser usar algo similar a ejecutar sum array . Vamos a crear 2 arreglos adicionales, de izquierda a derecha y de derecha a izquierda. Para la matriz leftToRigh, iteramos desde index = 1 hasta el final de la matriz y establecemos el valor en cada índice igual a la multiplicación del elemento actual y el valor anterior.

 int[] leftToRight = new int[nums.length]; leftToRight[0] = nums[0]; for (int i = 1; i < nums.length; i++) { leftToRight[i] = leftToRight[i - 1] * nums[i]; }

Si tenemos la entrada de [1, 2, 3, 4] entonces el código anterior nos da [1, 2, 6, 24]

Para rightToLeftarray iteramos desde index = array.length — 2 hasta el comienzo de la matriz y establecemos el valor en cada índice igual a la multiplicación del elemento actual y el valor anterior.

 int[] rightToLeft = new int[nums.length]; rightToLeft[nums.length - 1] = nums[nums.length - 1]; for (int i = nums.length - 2; i >= 0; i--) { rightToLeft[i] = rightToLeft[i + 1] * nums[i]; }

Si tenemos la entrada de [1, 2, 3, 4] entonces el código anterior nos da [24, 24, 12, 4]

Ahora que tenemos estas matrices, podemos simplemente calcular el producto de la matriz, excepto el elemento actual, iterando a través de cada índice y multiplicando los valores de izquierda a derecha y de derecha a izquierda. He aquí un ejemplo que le ayudará a comprender la lógica real.

Si tiene dificultades para entender la lógica, intente revisar las imágenes de arriba una vez más.

Echemos un vistazo a nuestra solución:

 public int[] productExceptSelf(int[] nums) { int[] leftToRight = new int[nums.length]; leftToRight[0] = nums[0]; for (int i = 1; i < nums.length; i++) { leftToRight[i] = leftToRight[i - 1] * nums[i]; } int[] rightToLeft = new int[nums.length]; rightToLeft[nums.length - 1] = nums[nums.length - 1]; for (int i = nums.length - 2; i >= 0; i--) { rightToLeft[i] = rightToLeft[i + 1] * nums[i]; } int[] answer = new int[nums.length]; for (int i = 0 ; i < answer.length; i++) { int left = i == 0 ? 1 : leftToRight[i - 1]; int right = i == answer.length - 1 ? 1 : rightToLeft[i + 1]; answer[i] = left * right; } return answer; }

Funciona y nos da un resultado decente:

PERO. Leamos la descripción de la tarea una vez más. En la parte inferior, tenemos una pregunta de seguimiento: para resolver el problema usando un espacio constante. Aquí usamos dos arreglos auxiliares.

Solución:

 public int[] productExceptSelf(int[] nums) { int[] answer = new int[nums.length]; Arrays.fill(answer, 1); int prev = 1; for (int i = 1; i < nums.length; i++) { answer[i] = prev * nums[i - 1]; prev = answer[i]; } prev = 1; for (int i = nums.length - 2; i >= 0; i--) { answer[i] *= prev * nums[i + 1]; prev *= nums[i + 1]; } return answer; }

Si lee atentamente la descripción, es posible que haya notado que la matriz de salida no cuenta como espacio adicional, es un truco. Al tener una matriz de entrada y una matriz de salida, todavía tenemos 2 matrices como leftToRight y rightToLeft que usamos en nuestra solución anterior. Solo necesitamos adaptar ligeramente nuestra lógica.

El código anterior nos da casi el mismo resultado pero usa el espacio constante O(1).

Déjame saber tu pensamiento. ¡Nos vemos en mis artículos!

También publicado aquí .