Dada uma matriz de números, retorne a matriz de produtos de todos os outros números (sem divisão)

Fiz essa pergunta em uma entrevista de emprego e gostaria de saber como os outros poderiam resolvê-la. Estou mais confortável com o Java, mas soluções em outros idiomas são bem-vindas.

Dada uma matriz de números, nums , retorna uma matriz de números products , onde products[i] é o produto de todos os 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] 

Você deve fazer isso em O(N) sem usar divisão.

Uma explicação do método dos poligenelubrificantes é: O truque é construir os arrays (no 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 podem ser feitos em O (n), iniciando nas bordas esquerda e direita, respectivamente.

Em seguida, multiplicar os dois arrays elemento por elemento dá o resultado desejado

Meu código seria algo como isto:

 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 

Se você precisa ser O (1) no espaço também você pode fazer isso (o que é menos claro IMHO)

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

Aqui está uma pequena function recursiva (em C ++) para fazer a modoficação no lugar. Requer O (n) espaço extra (na pilha) embora. Assumindo que o array está em a e N contém o comprimento do array, temos

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

Aqui está minha tentativa de resolvê-lo em Java. Desculpas para a formatação não-padrão, mas o código tem muita duplicação, e isso é o melhor que posso fazer para torná-lo legível.

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

As invariantes de loop são pi = nums[0] * nums[1] *.. nums[i-1] e pj = nums[N-1] * nums[N-2] *.. nums[j+1] . A parte i à esquerda é a lógica “prefixo”, e a parte j à direita é a lógica “sufixo”.


Recursiva one-liner

Jasmeet deu uma solução recursiva (linda!); Eu o transformei neste (horrível!) Linea de Java. Ele faz modificação no local , com O(N) espaço temporário na pilha.

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

Traduzindo a solução de Michael Anderson para Haskell:

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

Contornando furtivamente a regra “sem divisões”:

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

Aqui está, solução simples e limpa com complexidade 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. Viaje para a esquerda -> direita e continue salvando o produto. Chame isso passado. -> O (n)
  2. Vire à direita -> esquerda mantenha o produto. Chame isso de futuro. -> O (n)
  3. Resultado [i] = Passado [i-1] * futuro [i + 1] -> O (n)
  4. Passado [-1] = 1; e Futuro [n + 1] = 1;

Em)

Aqui está a minha solução no moderno C ++. Ele faz uso de std::transform e é bem fácil de lembrar.

Código online (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 é O (n ^ 2) mas f # é muuuuito bonito:

 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] 

Complicado:

Use o seguinte:

 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 

Sim, eu tenho certeza que eu perdi alguns i-1 ao invés de i, mas essa é a maneira de resolvê-lo.

Existe também uma solução não óptima de O (N ^ (3/2)). É bastante interessante, no entanto.

Primeiro, pré-processe cada multiplicação parcial de tamanho N ^ 0.5 (isso é feito em complexidade de tempo O (N)). Então, o cálculo para o múltiplo de outros valores de cada número pode ser feito em 2 * O (N ^ 0,5) tempo (por quê? Porque você precisa apenas múltiplos os últimos elementos de outros números (N ^ 0,5) – 1) e multiplique o resultado por ((N ^ 0.5) – 1) números que pertencem ao grupo do número atual). Fazendo isso para cada número, pode-se obter O (N ^ (3/2)) hora.

Exemplo:

4 6 7 2 3 1 9 5 8

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

Para calcular o valor de 3, é preciso multiplicar os valores dos outros grupos 168 * 360 e, em seguida, com 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); } } 

Esta solução eu vim com e achei tão claro o que você acha!

Pré-calcule o produto dos números à esquerda e à direita de cada elemento. Para cada elemento, o valor desejado é o produto de seus produtos.

 #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 

(UPDATE: agora eu olho mais de perto, isso usa o mesmo método que Michael Anderson, Daniel Migowski e poligenelubricantes acima)

 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 = [] produzir (arr, prod, 0) print prod

Adicionando a minha solução de javascript aqui como eu não encontrei ninguém sugerindo isso. O que é dividir, exceto para contar o número de vezes que você pode extrair um número de outro número? Eu passei por calcular o produto de toda a matriz e, em seguida, iterar sobre cada elemento e subtrair o elemento atual até zero:

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

Eu estou acostumado 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; } 

Bem, esta solução pode ser considerada a do C / C ++. Vamos dizer que temos uma matriz “a” contendo n elementos como um [n], então o pseudo código seria como abaixo.

 for(j=0;j 

Mais uma solução, usando divisão. com duas travessias. Multiplique todos os elementos e comece a dividi-lo por cada elemento.

 {-
 Solução recursiva usando subconjuntos sqrt (n).  Executa em O (n).

 Recursivamente calcula a solução em subconjuntos sqrt (n) de tamanho sqrt (n). 
 Em seguida, recurses na sum do produto de cada subconjunto.
 Então, para cada elemento em cada subconjunto, ele calcula o produto com
 a sum do produto de todos os outros produtos.
 Em seguida, achata todos os subconjuntos.

 Recorrência no tempo de execução é T (n) = sqrt (n) * T (sqrt (n)) + T (sqrt (n)) + n

 Suponha que T (n) ≤ cn em 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)

 Observe que o teto (sqrt (n)) pode ser calculado usando uma pesquisa binária 
 e O (logn) iterações, se a instrução sqrt não é permitida.
 -}

 otherProducts [] = []
 otherProducts [x] = [1]
 otherProducts [x, y] = [y, x]
 otherProducts a = foldl '(++) [] $ zipCom (\ sp -> map (* p) s) resolvidoSubsets subsetOtherProducts
     Onde 
       n = comprimento a

       - Tamanho do subconjunto  Exija que 1 

Aqui está o meu 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; } 

Aqui está um exemplo ligeiramente 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](); } } 

Eu não estou inteiramente certo de que isso é O (n), devido à semi-recursion dos Funcs criados, mas meus testes parecem indicar que é O (n) no tempo.

Para completar, aqui está o código em Scala:

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

Isso imprimirá o seguinte:

 120 60 40 30 24 

O programa filtrará o elem atual (_! = Elem); e multiplique a nova lista pelo método reduceLeft. Eu acho que isso será O (n) se você usar scala view ou Iterator para lazy eval.

// Esta é a solução recursiva em Java // Chamada como seguindo do produto 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; } 

Uma solução perfeita com o tempo de execução O (n):

  1. Para cada elemento calcule o produto de todos os elementos que ocorrem antes disso e armazene em uma matriz “pre”.
  2. Para cada elemento, calcule o produto de todos os elementos que ocorrem após esse elemento e armazene-o em uma matriz “post”
  3. Crie um array final “result”, para um 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)); 

Aqui está outro conceito simples que resolve o problema em 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 o nums[j] (onde j != i ) da lista primeiro, depois obter o produto do resto; O seguinte é uma python way para resolver este enigma:

 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] 

Com base na resposta do Billz – desculpe, não posso comentar, mas aqui está uma versão do scala que lida corretamente com itens duplicados na lista, e é provavelmente 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 

retorna:

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

Eu tenho uma solução com O(n) espaço e O(n^2) complexidade de tempo fornecida abaixo,

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