Dada una matriz de números, devuelve un conjunto de productos de todos los demás números (sin división)

Me hicieron esta pregunta en una entrevista de trabajo y me gustaría saber cómo lo resolverían otros. Estoy más cómodo con Java, pero las soluciones en otros idiomas son bienvenidas.

Dada una serie de números, nums , devuelve una matriz de números products , donde los products[i] son el producto de todos los nums[j], j != i

 Input : [1, 2, 3, 4, 5] Output: [(2*3*4*5), (1*3*4*5), (1*2*4*5), (1*2*3*5), (1*2*3*4)] = [120, 60, 40, 30, 24] 

Debes hacer esto en O(N) sin usar la división.

Una explicación del método polygenelubricants es: El truco es construir las matrices (en el caso de 4 elementos)

 { 1, a[0], a[0]*a[1], a[0]*a[1]*a[2], } { a[1]*a[2]*a[3], a[2]*a[3], a[3], 1, } 

Ambos se pueden hacer en O (n) comenzando por los bordes izquierdo y derecho, respectivamente.

Luego, multiplicando los dos arrays elemento por elemento da el resultado requerido

Mi código se vería así:

 int a[N] // This is the input int products_below[N]; p=1; for(int i=0;i=0;--i) { products_above[i]=p; p*=a[i]; } int products[N]; // This is the result for(int i=0;i 

Si necesita ser O (1) en el espacio también puede hacer esto (que es menos claro en mi humilde opinión)

 int a[N] // This is the input int products[N]; // Get the products below the current index p=1; for(int i=0;i=0;--i) { products[i]*=p; p*=a[i]; } 

Aquí hay una pequeña función recursiva (en C ++) para hacer la modificación en su lugar. Sin embargo, requiere O (n) espacio extra (en la stack). Suponiendo que la matriz está en ay N tiene la longitud de la matriz, tenemos

 int multiply(int *a, int fwdProduct, int indx) { int revProduct = 1; if (indx < N) { revProduct = multiply(a, fwdProduct*a[indx], indx+1); int cur = a[indx]; a[indx] = fwdProduct * revProduct; revProduct *= cur; } return revProduct; } 

Aquí está mi bash de resolverlo en Java. Disculpas por el formato no estándar, pero el código tiene mucha duplicación, y esto es lo mejor que puedo hacer para que sea legible.

 import java.util.Arrays; public class Products { static int[] products(int... nums) { final int N = nums.length; int[] prods = new int[N]; Arrays.fill(prods, 1); for (int i = 0, pi = 1 , j = N-1, pj = 1 ; (i < N) && (j >= 0) ; pi *= nums[i++] , pj *= nums[j--] ) { prods[i] *= pi ; prods[j] *= pj ; } return prods; } public static void main(String[] args) { System.out.println( Arrays.toString(products(1, 2, 3, 4, 5)) ); // prints "[120, 60, 40, 30, 24]" } } 

Las invariantes de bucle son pi = nums[0] * nums[1] *.. nums[i-1] y pj = nums[N-1] * nums[N-2] *.. nums[j+1] . La parte i a la izquierda es la lógica del “prefijo”, y la parte j a la derecha es la lógica del “sufijo”.


Recursivo de una sola línea

Jasmeet dio una (¡hermosa!) Solución recursiva; Lo he convertido en este (horrible!) Java one-liner. Hace una modificación in situ , con O(N) espacio temporal en la stack.

 static int multiply(int[] nums, int p, int n) { return (n == nums.length) ? 1 : nums[n] * (p = multiply(nums, nums[n] * (nums[n] = p), n + 1)) + 0*(nums[n] *= p); } int[] arr = {1,2,3,4,5}; multiply(arr, 1, 0); System.out.println(Arrays.toString(arr)); // prints "[120, 60, 40, 30, 24]" 

Traduciendo la solución de Michael Anderson en Haskell:

 otherProducts xs = zipWith (*) below above where below = scanl (*) 1 $ init xs above = tail $ scanr (*) 1 xs 

Sneakily eludir la regla de “no divisiones”:

 sum = 0.0 for i in range(a): sum += log(a[i]) for i in range(a): output[i] = exp(sum - log(a[i])) 

Aquí tienes, solución simple y limpia con complejidad O (N):

 int[] a = {1,2,3,4,5}; int[] r = new int[a.length]; int x = 1; r[0] = 1; for (int i=1;i0;i--){ x=x*a[i]; r[i-1]=x*r[i-1]; } for (int i=0;i 

C ++, O (n):

 long long prod = accumulate(in.begin(), in.end(), 1LL, multiplies()); transform(in.begin(), in.end(), back_inserter(res), bind1st(divides(), prod)); 
  1. Viaja hacia la izquierda y hacia la derecha y sigue guardando el producto. Llámalo Pasado. -> O (n)
  2. Viaje a la derecha -> a la izquierda, guarde el producto. Llámalo Futuro. -> O (n)
  3. Resultado [i] = Pasado [i-1] * futuro [i + 1] -> O (n)
  4. Pasado [-1] = 1; y Futuro [n + 1] = 1;

En)

Aquí está mi solución en C ++ moderno. Hace uso de std::transform y es bastante fácil de recordar.

Código en línea (wandbox).

 #include #include #include using namespace std; vector& multiply_up(vector& v){ v.insert(v.begin(),1); transform(v.begin()+1, v.end() ,v.begin() ,v.begin()+1 ,[](auto const& a, auto const& b) { return b*a; } ); v.pop_back(); return v; } int main() { vector v = {1,2,3,4,5}; auto vr = v; reverse(vr.begin(),vr.end()); multiply_up(v); multiply_up(vr); reverse(vr.begin(),vr.end()); transform(v.begin(),v.end() ,vr.begin() ,v.begin() ,[](auto const& a, auto const& b) { return b*a; } ); for(auto& i: v) cout << i << " "; } 

Este es O (n ^ 2) pero f # es tan hermoso:

 List.fold (fun seed i -> List.mapi (fun jx -> if i=j+1 then x else x*i) seed) [1;1;1;1;1] [1..5] 

Difícil:

Use lo siguiente:

 public int[] calc(int[] params) { int[] left = new int[n-1] in[] right = new int[n-1] int fac1 = 1; int fac2 = 1; for( int i=0; i 

Sí, estoy seguro de haber perdido algo de i-1 en lugar de i, pero esa es la manera de resolverlo.

También hay una solución no óptima O (N ^ (3/2)). Sin embargo, es bastante interesante.

Primero preprocesé cada multiplicación parcial de tamaño N ^ 0.5 (esto se hace en O (N) complejidad de tiempo). Entonces, el cálculo de los valores-otros-de cada número se puede hacer en 2 * O (N ^ 0.5) veces (¿por qué? Porque solo necesita multiplicar los últimos elementos de otros ((N ^ 0.5) – 1) números, y multiplica el resultado con ((N ^ 0.5) – 1) números que pertenecen al grupo del número actual). Haciendo esto para cada número, uno puede obtener O (N ^ (3/2)) tiempo.

Ejemplo:

4 6 7 2 3 1 9 5 8

resultados parciales: 4 * 6 * 7 = 168 2 * 3 * 1 = 6 9 * 5 * 8 = 360

Para calcular el valor de 3, se necesita multiplicar los valores de los otros grupos 168 * 360, y luego con 2 * 1.

 public static void main(String[] args) { int[] arr = { 1, 2, 3, 4, 5 }; int[] result = { 1, 1, 1, 1, 1 }; for (int i = 0; i < arr.length; i++) { for (int j = 0; j < i; j++) { result[i] *= arr[j]; } for (int k = arr.length - 1; k > i; k--) { result[i] *= arr[k]; } } for (int i : result) { System.out.println(i); } } 

Se me ocurrió esta solución y la encontré tan clara ¿qué opinas?

Precalcular el producto de los números a la izquierda y a la derecha de cada elemento. Para cada elemento, el valor deseado es el producto de sus productos.

 #include  unsigned array[5] = { 1,2,3,4,5}; int main(void) { unsigned idx; unsigned left[5] , right[5]; left[0] = 1; right[4] = 1; /* calculate products of numbers to the left of [idx] */ for (idx=1; idx < 5; idx++) { left[idx] = left[idx-1] * array[idx-1]; } /* calculate products of numbers to the right of [idx] */ for (idx=4; idx-- > 0; ) { right[idx] = right[idx+1] * array[idx+1]; } for (idx=0; idx <5 ; idx++) { printf("[%u] Product(%u*%u) = %u\n" , idx, left[idx] , right[idx] , left[idx] * right[idx] ); } return 0; } 

Resultado:

 $ ./a.out [0] Product(1*120) = 120 [1] Product(1*60) = 60 [2] Product(2*20) = 40 [3] Product(6*5) = 30 [4] Product(24*1) = 24 

(ACTUALIZACIÓN: ahora miro más de cerca, esto utiliza el mismo método que Michael Anderson, Daniel Migowski y polygenelubricants arriba)

 def productify(arr, prod, i): if i < len(arr): prod.append(arr[i - 1] * prod[i - 1]) if i > 0 else prod.append(1) retval = productify(arr, prod, i + 1) prod[i] *= retval return retval * arr[i] return 1 

arr = [1, 2, 3, 4, 5] prod = [] productify (arr, prod, 0) imprimir prod

Agregando mi solución de JavaScript aquí ya que no encontré a nadie sugiriendo esto. ¿Qué es dividir, excepto contar la cantidad de veces que puede extraer un número de otro número? Pasé por el cálculo del producto de la matriz completa, y luego iterar sobre cada elemento y restar el elemento actual hasta cero:

 //No division operation allowed // keep substracting divisor from dividend, until dividend is zero or less than divisor function calculateProducsExceptCurrent_NoDivision(input){ var res = []; var totalProduct = 1; //calculate the total product for(var i = 0; i < input.length; i++){ totalProduct = totalProduct * input[i]; } //populate the result array by "dividing" each value for(var i = 0; i < input.length; i++){ var timesSubstracted = 0; var divisor = input[i]; var dividend = totalProduct; while(divisor <= dividend){ dividend = dividend - divisor; timesSubstracted++; } res.push(timesSubstracted); } return res; } 

Estoy acostumbrado a C #:

  public int[] ProductExceptSelf(int[] nums) { int[] returnArray = new int[nums.Length]; List auxList = new List(); int multTotal = 0; // If no zeros are contained in the array you only have to calculate it once if(!nums.Contains(0)) { multTotal = nums.ToList().Aggregate((a, b) => a * b); for (int i = 0; i < nums.Length; i++) { returnArray[i] = multTotal / nums[i]; } } else { for (int i = 0; i < nums.Length; i++) { auxList = nums.ToList(); auxList.RemoveAt(i); if (!auxList.Contains(0)) { returnArray[i] = auxList.Aggregate((a, b) => a * b); } else { returnArray[i] = 0; } } } return returnArray; } 

Bueno, esta solución se puede considerar la de C / C ++. Digamos que tenemos una matriz “a” que contiene n elementos como a [n], y luego el pseudo código sería el siguiente.

 for(j=0;j 

Una solución más, usando la división. con dos travesías. Multiplica todos los elementos y luego comienza a dividirlos por cada elemento.

 {-
 Solución recursiva utilizando subconjuntos sqrt (n).  Se ejecuta en O (n).

 Recursivamente calcula la solución en sqrt (n) subconjuntos de tamaño sqrt (n). 
 Luego recurses en la sum del producto de cada subconjunto.
 Luego, para cada elemento en cada subconjunto, calcula el producto con
 la sum del producto de todos los demás productos.
 A continuación, aplana todos los subconjuntos.

 La recurrencia en el tiempo de ejecución es T (n) = sqrt (n) * T (sqrt (n)) + T (sqrt (n)) + n

 Supongamos que T (n) ≤ cn en O (n).

 T (n) = sqrt (n) * T (sqrt (n)) + T (sqrt (n)) + n
     ≤ sqrt (n) * c * sqrt (n) + c * sqrt (n) + n
     ≤ c * n + c * sqrt (n) + n
     ≤ (2c + 1) * n
     ∈ O (n)

 Tenga en cuenta que el techo (sqrt (n)) se puede calcular utilizando una búsqueda binaria 
 y O (logn) iteraciones, si la instrucción sqrt no está permitida.
 -}

 otrosProductos [] = []
 otherProducts [x] = [1]
 otherProducts [x, y] = [y, x]
 otherProducts a = foldl '(++) [] $ zipWith (\ sp -> map (* p) s) resueltoSubsets subconjuntoOtherProducts
     dónde 
       n = longitud a

       - Tamaño del subconjunto.  Requerir que 1 

Aquí está mi código:

 int multiply(int a[],int n,int nextproduct,int i) { int prevproduct=1; if(i>=n) return prevproduct; prevproduct=multiply(a,n,nextproduct*a[i],i+1); printf(" i=%d > %d\n",i,prevproduct*nextproduct); return prevproduct*a[i]; } int main() { int a[]={2,4,1,3,5}; multiply(a,5,1,0); return 0; } 

Aquí hay un ejemplo ligeramente funcional, usando C #:

  Func[] backwards = new Func[input.Length]; Func[] forwards = new Func[input.Length]; for (int i = 0; i < input.Length; ++i) { var localIndex = i; backwards[i] = () => (localIndex > 0 ? backwards[localIndex - 1]() : 1) * input[localIndex]; forwards[i] = () => (localIndex < input.Length - 1 ? forwards[localIndex + 1]() : 1) * input[localIndex]; } var output = new long[input.Length]; for (int i = 0; i < input.Length; ++i) { if (0 == i) { output[i] = forwards[i + 1](); } else if (input.Length - 1 == i) { output[i] = backwards[i - 1](); } else { output[i] = forwards[i + 1]() * backwards[i - 1](); } } 

No estoy del todo seguro de que esto sea O (n), debido a la semi-recursión de los Funcs creados, pero mis pruebas parecen indicar que es O (n) en el tiempo.

Para completar aquí está el código en Scala:

 val list1 = List(1, 2, 3, 4, 5) for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_)) 

Esto imprimirá lo siguiente:

 120 60 40 30 24 

El progtwig filtrará el elemento actual (_! = Elem); y multiplique la nueva lista con el método reductionLeft. Creo que esto será O (n) si usa scala view o Iterator para lazy eval.

// Esta es la solución recursiva en Java // Llamada como siguiente del producto principal (a, 1,0);

 public static double product(double[] a, double fwdprod, int index){ double revprod = 1; if (index < a.length){ revprod = product2(a, fwdprod*a[index], index+1); double cur = a[index]; a[index] = fwdprod * revprod; revprod *= cur; } return revprod; } 

Una solución ordenada con tiempo de ejecución O (n):

  1. Para cada elemento, calcule el producto de todos los elementos que ocurren antes de eso y almacene en una matriz “pre”.
  2. Para cada elemento, calcule el producto de todos los elementos que ocurren después de ese elemento y guárdelo en una matriz “publicar”
  3. Crea un “resultado” de matriz final, para un elemento i,

     result[i] = pre[i-1]*post[i+1]; 
 function solution($array) { $result = []; foreach($array as $key => $value){ $copyOfOriginalArray = $array; unset($copyOfOriginalArray[$key]); $result[$key] = multiplyAllElemets($copyOfOriginalArray); } return $result; } /** * multiplies all elements of array * @param $array * @return int */ function multiplyAllElemets($array){ $result = 1; foreach($array as $element){ $result *= $element; } return $result; } $array = [1, 9, 2, 7]; print_r(solution($array)); 

Aquí hay otro concepto simple que resuelve el problema en O(N) .

  int[] arr = new int[] {1, 2, 3, 4, 5}; int[] outArray = new int[arr.length]; for(int i=0;i a * b); outArray[i] = res/arr[i]; } System.out.println(Arrays.toString(outArray)); 

Podemos excluir los nums[j] (donde j != i ) de la lista primero, luego obtener el producto del rest; La siguiente es una python way para resolver este rompecabezas:

 def products(nums): return [ reduce(lambda x,y: x * y, nums[:i] + nums[i+1:]) for i in range(len(nums)) ] print products([1, 2, 3, 4, 5]) [out] [120, 60, 40, 30, 24] 

Basado en la respuesta de Billz: lo siento, no puedo comentar, pero aquí hay una versión de Scala que maneja correctamente los elementos duplicados en la lista, y probablemente sea O (n):

 val list1 = List(1, 7, 3, 3, 4, 4) val view = list1.view.zipWithIndex map { x => list1.view.patch(x._2, Nil, 1).reduceLeft(_*_)} view.force 

devoluciones:

 List(1008, 144, 336, 336, 252, 252) 

Tengo una solución con O(n) espacio y O(n^2) complejidad de tiempo proporcionada a continuación,

 public static int[] findEachElementAsProduct1(final int[] arr) { int len = arr.length; // int[] product = new int[len]; // Arrays.fill(product, 1); int[] product = IntStream.generate(() -> 1).limit(len).toArray(); for (int i = 0; i < len; i++) { for (int j = 0; j < len; j++) { if (i == j) { continue; } product[i] *= arr[j]; } } return product; }