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

Это O (n ^ 2), но f # так красиво:

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]

Хитрость:

Используйте следующее:

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

Да, я уверен, что пропустил i-1 вместо i, но это способ реши это.

Вот моя попытка решить эту проблему на Java. Приносим извинения за нестандартное форматирование, но в коде много дублирования, и это лучшее, что я могу сделать, чтобы сделать его читабельным.

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

Инварианты цикла: pi = nums [0] * nums [1] * .. nums [i-1] и pj = nums [N-1] * nums [N- 2] * .. число [j + 1] . Часть i слева - это логика «префикса», а часть j справа - логика «суффикса».

Рекурсивный однострочный

Джасмит дал (красивое!) Рекурсивное решение; Я превратил его в этот (отвратительный!) Однострочник Java. Он выполняет модификацию на месте с временным пространством в стеке O (N) .

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

Перевод решения Майкла Андерсона на Haskell:

otherProducts xs = zipWith (*) below above

     where below = scanl (*) 1 $ init xs

           above = tail $ scanr (*) 1 xs

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

Что ж, это решение можно считать решением C / C ++. { {1}} Допустим, у нас есть массив "a", содержащий n элементов , например a [n], тогда псевдокод будет таким, как показано ниже.

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

Вот небольшая рекурсивная функция (в C ++) для модификации на месте. Однако для этого требуется O (n) дополнительного места (в стеке). Предполагая, что массив находится в a, а N содержит длину массива, мы имеем

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

Подлый обход правила «без разделения»:

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

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

Также существует O (N ^ (3/2)) неоптимальное решение. Но это довольно интересно.

Сначала предварительно обработайте каждое частичное умножение размера N ^ 0,5 (это делается с временной сложностью O (N)). Затем вычисление для каждого числа, кратного другим значениям, может быть выполнено за 2 * O (N ^ 0,5) раз (почему? Потому что вам нужно только умножить последние элементы других ((N ^ 0,5) - 1) чисел, и умножьте результат на ((N ^ 0,5) - 1) числа, принадлежащие группе текущего числа). Проделав это для каждого числа, можно получить время O (N ^ (3/2)).

Пример:

4 6 7 2 3 1 9 5 8

частичные результаты: 4 * 6 * 7 = 168 2 * 3 * 1 = 6 9 * 5 * 8 = 360

Чтобы вычислить значение 3, нужно умножить значения других групп 168 * 360, а затем на 2 * 1.

Еще одно решение, использующее деление. с двойным обходом. Умножьте все элементы, а затем начните делить их на каждый элемент.

    int[] arr1 = { 1, 2, 3, 4, 5 };
    int[] product = new int[arr1.Length];              

    for (int i = 0; i < arr1.Length; i++)
    {
        for (int j = 0; j < product.Length; j++)
        {
            if (i != j)
            {
                product[j] = product[j] == 0 ? arr1[i] : product[j] * arr1[i];
            }
        }
    }