Étant donné un tableau de nombres, renvoie un tableau de produits de tous les autres nombres (pas de division).

Question

Cette question m'a été posée lors d'un entretien d'embauche et j'aimerais savoir comment d'autres personnes y répondraient. Je suis plus à l'aise avec Java, mais les solutions dans d'autres langages sont les bienvenues.

Étant donné un tableau de nombres, nums et renvoie un tableau de nombres products donde products[i] est le produit de tous les 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]

Vous devez le faire dans O(N) sans utiliser la division.

Answer 1

Une explication de lubrifiants polygéniques est la méthode :

L'astuce consiste à construire les tableaux (dans le cas de 4 éléments) :

{              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,  }

Ces deux opérations peuvent être effectuées en O(n) en commençant respectivement par les bords gauche et droit.

Ensuite, en multipliant les deux tableaux élément par élément, on obtient le résultat souhaité.

Mon code ressemblerait à ceci :

int a[N] // This is the input
int products_below[N];
int 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 vous voulez que la solution soit également O(1) dans l'espace, vous pouvez faire ceci (ce qui est moins clair à mon avis) :

int a[N] // This is the input
int products[N];

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

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

Answer 2

Voici une petite fonction récursive (en C++) pour effectuer la modification sur place. Elle nécessite cependant O(n) espace supplémentaire (sur la pile). En supposant que le tableau soit dans a y N contient la longueur du tableau, nous avons :

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 3

Voici ma tentative de résoudre ce problème en Java. Je m'excuse pour le formatage non standard, mais le code comporte de nombreuses répétitions et c'est le mieux que je puisse faire pour le rendre lisible.

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

Les invariants de la boucle sont pi = nums[0] * nums[1] *.. nums[i-1] y pj = nums[N-1] * nums[N-2] *.. nums[j+1] . Les i La partie de gauche est la logique du "préfixe", et la partie de droite est la logique du "préfixe". j La partie droite est la logique du "suffixe".

---

Un seul scénario récursif

Jasmeet a donné une solution récursive (magnifique !); je l'ai transformée en ce one-liner Java (hideux !). Il fait modification en place , avec O(N) un espace temporaire dans la pile.

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 4

Traduction de la solution de Michael Anderson en Haskell :

otherProducts xs = zipWith (*) below above

     where below = scanl (*) 1 $ init xs

           above = tail $ scanr (*) 1 xs

Answer 5

Contourner subrepticement la règle "pas de division" :

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

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