Descripción de la tarea:  Dada una matriz de enteros   , devuelva una                 . nums answer de matriz tal que answer[i] sea igual al producto de todos los elementos de nums excepto nums[i]  Se   que el producto de cualquier prefijo o sufijo de   cabe en un número entero   . garantiza nums de 32 bits  Debes escribir un algoritmo que se ejecute en tiempo   y sin usar la operación de división. O(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   que el producto de cualquier prefijo o sufijo de   cabe en un número entero   . garantiza nums de 32 bits    ¿Puedes resolver el problema en la complejidad del espacio extra   ? (La matriz de salida   cuenta como espacio adicional para el análisis de complejidad espacial). Seguimiento: O(1) no  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   . 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. ejecutar sum array  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í

2022 - HackerNoon Contributor of the Year - Algorithms

2022 - HackerNoon Contributor of the Year - Coding

2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Algorithms

Nominated for 2022 - HackerNoon Contributor of the Year - Java

Nominated for 2022 - HackerNoon Contributor of the Year - Coding

Este audio es producido en el idioma original de la historia!

Demasiado Largo; Para Leer

Make resilience your competitive advantage

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

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

Liberando el poder de la IA. Una revisión sistemática de técnicas de vanguardia: resumen e introducción

Valhalla de Floki se une como patrocinador asociado de la gira de la India por Sri Lanka

Aumente su productividad con estas 18 herramientas para desarrolladores 🚀🔥

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

Liberando el poder de la IA. Una revisión sistemática de técnicas de vanguardia: resumen e introducción

Valhalla de Floki se une como patrocinador asociado de la gira de la India por Sri Lanka

Aumente su productividad con estas 18 herramientas para desarrolladores 🚀🔥

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps