Dada una matriz de n enteros donde n> 1, nums, devuelve una salida de matriz tal que la salida[i] es igual al producto de todos los elementos de nums excepto nums[i].
Resuélvelo sin división y en O (n).
Por ejemplo, dado [1,2,3,4], regreso [24,12,8,6].
Solución Java 1
public int[] productExceptSelf(int[] nums) { int[] result = new int[nums.length]; int[] t1 = new int[nums.length]; int[] t2 = new int[nums.length]; t1[0]=1; t2[nums.length-1]=1; //scan from left to right for(int i=0; i<nums.length-1; i++){ t1[i+1] = nums[i] * t1[i]; } //scan from right to left for(int i=nums.length-1; i>0; i--){ t2[i-1] = t2[i] * nums[i]; } //multiply for(int i=0; i<nums.length; i++){ result[i] = t1[i] * t2[i]; } return result; } |
Solución Java 2
Podemos poner directamente los valores del producto en la matriz de resultados finales. Esto ahorra espacio adicional para almacenar las 2 matrices intermedias en la Solución 1.
public int[] productExceptSelf(int[] nums) { int[] result = new int[nums.length]; result[nums.length-1]=1; for(int i=nums.length-2; i>=0; i--){ result[i]=result[i+1]*nums[i+1]; } int left=1; for(int i=0; i<nums.length; i++){ result[i]=result[i]*left; left = left*nums[i]; } return result; } |
