Решение задачи кодирования «Произведение массива, кроме себя»

Введение. Задача «Произведение массива, кроме самого себя» — это распространенная задача кодирования, требующая нахождения произведения всех элементов массива, кроме элемента с текущим индексом. Задача состоит в том, чтобы решить ее без использования деления и за O(n) временной сложности. Кроме того, последующий вопрос спрашивает, можно ли решить его с постоянной пространственной сложностью. В этой статье мы рассмотрим эффективный алгоритм решения этой проблемы и обсудим решения как оптимальной временной, так и пространственной сложности.

Постановка задачи: задан массив из n целых чисел, где n > 1, задача состоит в том, чтобы вернуть выходной массив, такой что output[i] равен произведению всех элементов входного массива, кроме nums[i].

Пример: при заданном входном массиве nums = [1, 2, 3, 4] алгоритм должен вернуть выходной массив [24, 12, 8, 6], так как произведение всех элементов, кроме nums[0], равно 24, произведение всех элементов, кроме nums[1], равно 12 и так далее.

Алгоритм: Чтобы решить эту проблему без использования деления и с временной сложностью O(n), мы можем использовать тот факт, что произведение всех элементов, кроме текущего, может быть вычислено путем умножения произведения всех элементов слева от текущего элемент с произведением всех элементов справа от текущего элемента.

Вот алгоритм достижения этого:

1. Инициализировать выходной массив той же длины, что и входной массив, изначально заполненный 1.
2. Переберите входной массив слева направо и для каждого элемента обновите выходной массив, умножив текущий продукт на произведение всех элементов слева от текущего элемента.
3. Сбросьте текущий продукт до 1 и снова выполните цикл по входному массиву, но на этот раз справа налево. Для каждого элемента обновите выходной массив, умножив текущий продукт на произведение всех элементов справа от текущего элемента, и обновите текущий продукт, умножив его на текущий элемент.
4. Верните выходной массив, который теперь содержит произведение всех элементов, кроме текущего элемента по каждому индексу.

Этот алгоритм имеет временную сложность O(n), так как мы дважды перебираем входной массив, и пространственную сложность O(n), поскольку мы используем дополнительный выходной массив той же длины, что и входной массив.

Реализация:
Вот реализация алгоритма в коде C:

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
 
    int total=1;
    int i=0;
    int zero=0;
    int* ans=(int*)malloc(sizeof(int)*numsSize);
 
    *returnSize=numsSize;
 
    for(i=0;i<numsSize;i++)
    {
        if(nums[i]!=0)
          total*=nums[i];
        else
          zero++;
    }
 
    if(zero>1)//all zero
    total=0;
 
    if(zero>0)
    {
        for(i=0;i<numsSize;i++)
        {
            if(nums[i]==0)
                ans[i]=total;
            else
                ans[i]=0;
        }
    }else
    {
        for(i=0;i<numsSize;i++)
        {
            ans[i]=total/nums[i];
        }
    }
 
    return ans;
 
}
Loop through the input array from left to right, and for each element, update the current product with the product of all elements to the left of the current element.

1. Сбросьте текущий продукт до 1 и снова выполните цикл по входному массиву, но на этот раз справа налево.

return ans;

}