arrays - resueltos - vectores y matrices en programacion

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

Question

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.

Answer 1

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)

Answer 2

// 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;
}

Answer 3

Aquí está la versión de ptyhon

 # This solution use O(n) time and O(n) space
def productExceptSelf(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
N = len(nums)
if N == 0: return
# Initialzie list of 1, size N
l_prods, r_prods = [1]*N, [1]*N
for i in range(1, N):
l_prods[i] = l_prods[i-1] * nums[i-1]
for i in reversed(range(N-1)):
r_prods[i] = r_prods[i+1] * nums[i+1]
result = [x*y for x,y in zip(l_prods,r_prods)]
return result
# This solution use O(n) time and O(1) space
def productExceptSelfSpaceOptimized(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
N = len(nums)
if N == 0: return
# Initialzie list of 1, size N
result = [1]*N
for i in range(1, N):
result[i] = result[i-1] * nums[i-1]
r_prod = 1
for i in reversed(range(N)):
result[i] *= r_prod
r_prod *= nums[i]
return result

Answer 4

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;
}

Answer 5

Aquí está mi intento 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 pila.

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]"

Answer 6

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<algorithm>
#include<iostream>
#include<vector>
using namespace std;
vector<int>& multiply_up(vector<int>& 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<int> 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 << " ";
}

Answer 7

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<arr.length;i++){
int res=Arrays.stream(arr).reduce(1, (a, b) -> a * b);
outArray[i] = res/arr[i];
}
System.out.println(Arrays.toString(outArray));

Answer 8

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

 Func<long>[] backwards = new Func<long>[input.Length];
Func<long>[] forwards = new Func<long>[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.

Answer 9

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 pila). 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;
}

Answer 10

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;i<a.length;i++){
r[i]=r[i-1]*a[i-1];
}
for (int i=a.length-1;i>0;i--){
x=x*a[i];
r[i-1]=x*r[i-1];
}
for (int i=0;i<r.length;i++){
System.out.println(r[i]);
}

Answer 11

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)

Answer 12

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<n;j++)
{
prod[j]=1;
for (i=0;i<n;i++)
{
if(i==j)
continue;
else
prod[j]=prod[j]*a[i];
}

Answer 13

C ++, O (n):

long long prod = accumulate(in.begin(), in.end(), 1LL, multiplies<int>());
transform(in.begin(), in.end(), back_inserter(res),
bind1st(divides<long long>(), prod));

Answer 14

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<n; i++ ) {
fac1 = fac1 * params[i];
fac2 = fac2 * params[n-i];
left[i] = fac1;
right[i] = fac2;
}
fac = 1;
int[] results = new int[n];
for( int i=0; i<n; i++ ) {
results[i] = left[i] * right[i];
}

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

Answer 15

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

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

Answer 16

Me hicieron esta pregunta recientemente, y aunque no pude obtener O (N) durante el mismo, tuve un enfoque diferente (desafortunadamente O (N ^ 2)) pero pensé que lo compartiría de todos modos.

Convertir a la List<Integer> primero.

array.length() por la matriz original array.length() veces.

Use un ciclo while para multiplicar el siguiente conjunto de números requeridos:

while (temp < list.size() - 1) {
res *= list.get(temp);
temp++;
}

A continuación, agregue res a una nueva matriz (que por supuesto ha declarado anteriormente), luego agregue el valor en la array[i] a la List , y continúe así.

Sé que esto no será de gran utilidad, pero es lo que surgió bajo las presiones de una entrevista :)

 int[] array = new int[]{1, 2, 3, 4, 5};
List<Integer> list = Arrays.stream(array).boxed().collect(Collectors.toList());
int[] newarray = new int[array.length];
int res = 1;
for (int i = 0; i < array.length; i++) {
int temp = i;
while (temp < list.size() - 1) {
res *= list.get(temp);
temp++;
}
newarray[i] = res;
list.add(array[i]);
res = 1;
}

Salida: [24, 120, 60, 40, 30]

Answer 17

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 programa 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.

Answer 18

Podemos excluir los nums[j] (donde j != i ) de la lista primero, luego obtener el producto del resto; 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]

Answer 19

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 <stdio.h>
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)

Answer 20

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]))

Answer 21

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.

Answer 22

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;
}

Answer 23

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

Answer 24

Una explicación del método 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<N;++i) {
products_below[i]=p;
p*=a[i];
}
int products_above[N];
p=1;
for(int i=N-1;i>=0;--i) {
products_above[i]=p;
p*=a[i];
}
int products[N]; // This is the result
for(int i=0;i<N;++i) {
products[i]=products_below[i]*products_above[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<N;++i) {
products[i]=p;
p*=a[i];
}
// Get the products above the curent index
p=1;
for(int i=N-1;i>=0;--i) {
products[i]*=p;
p*=a[i];
}

Answer 25

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.

Answer 26

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];

Answer 27

{- Recursive solution using sqrt(n) subsets. Runs in O(n). Recursively computes the solution on sqrt(n) subsets of size sqrt(n). Then recurses on the product sum of each subset. Then for each element in each subset, it computes the product with the product sum of all other products. Then flattens all subsets. Recurrence on the run time is T(n) = sqrt(n)*T(sqrt(n)) + T(sqrt(n)) + n Suppose that T(n) ≤ cn in 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 &in; O(n) Note that ceiling(sqrt(n)) can be computed using a binary search and O(logn) iterations, if the sqrt instruction is not permitted. -} otherProducts [] = [] otherProducts [x] = [1] otherProducts [x,y] = [y,x] otherProducts a = foldl'' (++) [] $ zipWith (/s p -> map (*p) s) solvedSubsets subsetOtherProducts where n = length a -- Subset size. Require that 1 < s < n. s = ceiling $ sqrt $ fromIntegral n solvedSubsets = map otherProducts subsets subsetOtherProducts = otherProducts $ map product subsets subsets = reverse $ loop a [] where loop [] acc = acc loop a acc = loop (drop s a) ((take s a):acc)

Answer 28

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

Answer 29

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));

Answer 30

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?