Puzzle .. résoudre le produit des valeurs dans le tableau X

Question

Pouvez-vous m'aider s'il vous plaît à résoudre celui-ci?

Vous avez un tableau non ordonné X de n entiers. Trouver le tableau M contenant n éléments où Mi est le produit de tous les entiers de X sauf pour Xi. Vous ne pouvez pas utiliser la division. Vous pouvez utiliser de la mémoire supplémentaire. (Indice: il y a des solutions plus rapides que O (n^2).)

Les fonctions de base - O (n^2) et celle utilisant la division sont faciles. Mais je ne peux pas obtenir une autre solution plus rapide que O (n^2).

Answer 1

Soit left[i] être le produit de tous les éléments de X de 1..i. Soit right[i] être le produit de tous les éléments de X de i..N. Vous pouvez calculer les deux en O(n) sans division de la façon suivante: left[i] = left[i - 1] * X[i] et right[i] = right[i + 1] * X[i];

Maintenant, nous allons calculer M: M[i] = left[i - 1] * right[i + 1]

Note: left et right sont des tableaux.

L'espoir, il est clair :)

Answer 2

est ici une solution en Python. J'ai fait le chemin facile avec la division pour comparer à la dure sans. Est-ce que je reçois le travail?

L = [2, 1, 3, 5, 4] 

prod = 1 
for i in L: prod *= i 
easy = map(lambda x: prod/x, L) 
print easy 

hard = [1]*len(L) 
hmm = 1 
for i in range(len(L) - 1): 
    hmm *= L[i] 
    hard[i + 1] *= hmm 
huh = 1 
for i in range(len(L) - 1, 0, -1): 
    huh *= L[i] 
    hard[i - 1] *= huh 
print hard 

Answer 3

O(nlogn) approche:

int multiply(int arr[], int start, int end) { 
    int mid; 
    if (start > end) { 
     return 1; 
    } 
    if (start == end) { 
     return arr[start]; 
    } 
    mid = (start+end)/2; 
    return (multiply(arr, start, mid)*multiply(arr, mid+1, end)); 
} 

int compute_mi(int arr[], int i, int n) { 
    if ((i >= n) || (i < 0)) { 
     return 0; 
    } 

    return (multiply(arr, 0, i-1)*multiply(arr, i+1, n-1)); 
} 

Answer 4

O(n) - http://nbl.cewit.stonybrook.edu:60128/mediawiki/index.php/TADM2E_3.28

deux passes -

int main (int argc, char **argv) { 
    int array[] = {2, 5, 3, 4}; 
    int fwdprod[] = {1, 1, 1, 1}; 
    int backprod[] = {1, 1, 1, 1}; 
    int mi[] = {1, 1, 1, 1}; 
    int i, n = 4; 
    for (i=1; i<=n-1; i++) { 
     fwdprod[i]=fwdprod[i-1]*array[i-1]; 
    } 
    for (i=n-2; i>=0; i--) { 
     backprod[i] = backprod[i+1]*array[i+1]; 
    } 
    for (i=0;i<=n-1;i++) { 
     mi[i]=fwdprod[i]*backprod[i]; 
    } 
    return 0; 
} 

Answer 5

vieux mais très cool, on m'a demandé cela à une entrevue et moi-même vu plusieurs solutions depuis mais c'est mon préféré comme pris de http://www.polygenelubricants.com/2010/04/on-all-other-products-no-division.html

static int[] products(int... nums) { 
     final int N = nums.length; 
     int[] prods = new int[N]; 
     java.util.Arrays.fill(prods, 1); 
     for (int // pi----> * <----pj 
      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 ; 
      System.out.println("pi up to this point is " + pi + "\n"); 
      System.out.println("pj up to this point is " + pj + "\n"); 
      System.out.println("prods[i]:" + prods[i] + "pros[j]:" + prods[j] + "\n"); 
     } 
     return prods; 
    } 

Voici ce qui se passe, si vous écrivez aiguillons [i] pour toutes les itérations, vous verrez ce qui suit étant calculé

prods[0], prods[n-1] 
prods[1], prods[n-2] 
prods[2], prods[n-3] 
prods[3], prods[n-4] 
. 
. 
. 
prods[n-3], prods[2] 
prods[n-2], prods[1] 
prods[n-1], prods[0] 

de sorte que chaque aiguillons [i] get frapper deux fois, un de l'aller de la tête à la queue et une fois de la queue à la tête, et ces deux itérations accumulent le produit comme ils traversent vers le centre de sorte qu'il est facile de voir que nous aurons exactement ce dont nous avons besoin, nous venons besoin d'être prudent et de voir qu'il manque l'élément lui-même et c'est là que ça devient compliqué. la clé réside dans la

pi *= nums[i++], pj *= nums[j--] 

dans la boucle elle-même conditionnelle et non pas dans le corps qui ne se produit pas jusqu'à la fin de la itération. Donc, pour prods[0], il commence à 1 * 1, puis pi se prépare à 120 après, de sorte que aiguillons [0] manque le premiers éléments prods[1], est de 1 * 120 = 120, puis pi se prépare à 120 * 60 après etc. et ainsi de suite