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

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

Объяснение полигенных смазок метод: Хитрость заключается в том, чтобы построить массивы (в случае для 4 элементов)

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

И то, и другое можно сделать в O (n), начиная с левого и правого краев соответственно.

Затем умножение двух элементов массива на элемент дает требуемый результат

Мой код будет выглядеть примерно так:

int a[N] // This is the input
int products_below[N];
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];
}

Если вам нужно быть O (1) в космосе, вы можете сделать это (что менее понятно, ИМХО)

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

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

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

Answer 2

Вот небольшая рекурсивная функция (в 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;
}

Answer 3

Вот моя попытка решить это на 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] *.. nums[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]"

Answer 4

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

otherProducts xs = zipWith (*) below above

     where below = scanl (*) 1 $ init xs

           above = tail $ scanr (*) 1 xs

Answer 5

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

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

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

Answer 6

Вот, пожалуйста, простое и чистое решение со сложностью 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;i<a.length;i++){
        r[i]=r[i-1]*a[i-1];
    }
    for (int i=a.length-1;i>0;i--){
        x=x*a[i];
        r[i-1]=x*r[i-1];
    }
    for (int i=0;i<r.length;i++){
        System.out.println(r[i]);
    }

Answer 7

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

Answer 8

1. Путешествуйте влево-> Вправо и сохраняйте продукт. Назовите это в прошлом. -> O (n)
2. Движение вправо -> влево сохранить товар. Назовите это Будущее. -> O (n)
3. Результат [i] = Прошлое [i-1] * Будущее [i + 1] -> O (n)
4. Прошлое [-1] = 1; и будущее [n + 1] = 1;

О (п)

Answer 9

Вот мое решение в современном C ++. Он использует std::transform и довольно легко запоминается.

Код онлайн (wandbox).

#include<algorithm>
#include<iostream>
#include<vector>

using namespace std;

vector<int>& multiply_up(vector<int>& 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<int> 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 << " "; 
}

Answer 10

Это 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]