Учитывая массив чисел, вернуть массив произведений всех других чисел (без деления)

Question

Мне задали этот вопрос на собеседовании, и я хотел бы знать, как другие решат его. Мне больше всего нравится Java, но приветствуются решения на других языках.

Учитывая массив чисел, nums, вернуть массив чисел products, где products[i] - произведение всех 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]

Вы должны сделать это в O(N) без использования деления.

Answer 1

// Это рекурсивное решение в Java // Вызывается следующим образом из основного продукта (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 2

int[] b = new int[] { 1, 2, 3, 4, 5 };            
int j;
for(int i=0;i<b.Length;i++)
{
  int prod = 1;
  int s = b[i];
  for(j=i;j<b.Length-1;j++)
  {
    prod = prod * b[j + 1];
  }
int pos = i;    
while(pos!=-1)
{
  pos--;
  if(pos!=-1)
     prod = prod * b[pos];                    
}
Console.WriteLine("\n Output is {0}",prod);
}

Answer 3

Чистое решение с O (n) временем выполнения:

1. Для каждого элемента рассчитайте произведение всех элементов, которые встречаются до этого, и сохраните его в массиве «pre».
2. Для каждого элемента рассчитайте произведение всех элементов, встречающихся после этого элемента, и сохраните его в массиве «post»

3. Создать окончательный массив "result" для элемента i,

   result[i] = pre[i-1]*post[i+1];