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

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

Существует также 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.

Answer 2

Хитрый:

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

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, но это способ решить эту проблему.

Answer 3

Для полноты вот код в Scala:

val list1 = List(1, 2, 3, 4, 5)
for (elem <- list1) println(list1.filter(_ != elem) reduceLeft(_*_))

Это напечатает следующее:

120
60
40
30
24

Программа отфильтрует текущий элемент (_! = Elem); и умножьте новый список с помощью метода reduLeft. Я думаю, что это будет O (n), если вы используете scala view или Iterator для lazy eval.

Answer 4

def productify(arr, prod, i):
    if i < len(arr):
            prod.append(arr[i - 1] * prod[i - 1]) if i > 0 else prod.append(1)
            retval = productify(arr, prod, i + 1)
            prod[i] *= retval
            return retval * arr[i]
    return 1

обр = [1, 2, 3, 4, 5] prod = [] производить (обр., изд., 0) продукт печати

Answer 5

Добавление моего решения javascript здесь, так как я не нашел никого, кто предлагал бы это. Что нужно разделить, кроме как посчитать, сколько раз вы можете извлечь число из другого числа? Я провел вычисление произведения всего массива, а затем перебрал все элементы и вычел текущий элемент до нуля:

//No division operation allowed
// keep substracting divisor from dividend, until dividend is zero or less than divisor
function calculateProducsExceptCurrent_NoDivision(input){
  var res = [];
  var totalProduct = 1;
  //calculate the total product
  for(var i = 0; i < input.length; i++){
    totalProduct = totalProduct * input[i];
  }
  //populate the result array by "dividing" each value
  for(var i = 0; i < input.length; i++){
    var timesSubstracted = 0;
    var divisor = input[i];
    var dividend = totalProduct;
    while(divisor <= dividend){
      dividend = dividend - divisor;
      timesSubstracted++;
    }
    res.push(timesSubstracted);
  }
  return res;
}

Answer 6

Пересчитайте произведение чисел слева и справа от каждого элемента. Для каждого элемента желаемое значение является продуктом продуктов его соседей.

#include <stdio.h>

unsigned array[5] = { 1,2,3,4,5};

int main(void)
{
unsigned idx;

unsigned left[5]
        , right[5];
left[0] = 1;
right[4] = 1;

        /* calculate products of numbers to the left of [idx] */
for (idx=1; idx < 5; idx++) {
        left[idx] = left[idx-1] * array[idx-1];
        }

        /* calculate products of numbers to the right of [idx] */
for (idx=4; idx-- > 0; ) {
        right[idx] = right[idx+1] * array[idx+1];
        }

for (idx=0; idx <5 ; idx++) {
        printf("[%u] Product(%u*%u) = %u\n"
                , idx, left[idx] , right[idx]  , left[idx] * right[idx]  );
        }

return 0;
}

Результат:

$ ./a.out
[0] Product(1*120) = 120
[1] Product(1*60) = 60
[2] Product(2*20) = 40
[3] Product(6*5) = 30
[4] Product(24*1) = 24

(ОБНОВЛЕНИЕ: теперь я посмотрю поближе, в нем используется тот же метод, что и у Майкла Андерсона, Даниэля Миговски и полигеносмазочных материалов, указанных выше)

Answer 7

public static void main(String[] args) {
    int[] arr = { 1, 2, 3, 4, 5 };
    int[] result = { 1, 1, 1, 1, 1 };
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < i; j++) {
            result[i] *= arr[j];

        }
        for (int k = arr.length - 1; k > i; k--) {
            result[i] *= arr[k];
        }
    }
    for (int i : result) {
        System.out.println(i);
    }
}

Это решение, которое я придумал, и я нашел его настолько ясным, что вы думаете!?

Answer 8

Основано на ответе Билла - извините, я не могу комментировать, но вот версия scala, которая правильно обрабатывает дублирующиеся элементы в списке и, вероятно, O (n):

val list1 = List(1, 7, 3, 3, 4, 4)
val view = list1.view.zipWithIndex map { x => list1.view.patch(x._2, Nil, 1).reduceLeft(_*_)}
view.force

возвращает:

List(1008, 144, 336, 336, 252, 252)

Answer 9

Я использую C #:

    public int[] ProductExceptSelf(int[] nums)
    {
        int[] returnArray = new int[nums.Length];
        List<int> auxList = new List<int>();
        int multTotal = 0;

        // If no zeros are contained in the array you only have to calculate it once
        if(!nums.Contains(0))
        {
            multTotal = nums.ToList().Aggregate((a, b) => a * b);

            for (int i = 0; i < nums.Length; i++)
            {
                returnArray[i] = multTotal / nums[i];
            }
        }
        else
        {
            for (int i = 0; i < nums.Length; i++)
            {
                auxList = nums.ToList();
                auxList.RemoveAt(i);
                if (!auxList.Contains(0))
                {
                    returnArray[i] = auxList.Aggregate((a, b) => a * b);
                }
                else
                {
                    returnArray[i] = 0;
                }
            }
        }            

        return returnArray;
    }

Answer 10

Мы можем сначала исключить nums[j] (где j != i) из списка, а затем получить произведение остальных; Ниже приведено python way, чтобы решить эту загадку:

def products(nums):
    return [ reduce(lambda x,y: x * y, nums[:i] + nums[i+1:]) for i in range(len(nums)) ]
print products([1, 2, 3, 4, 5])

[out]
[120, 60, 40, 30, 24]