Постановка задачи

Дан целочисленный массив nums, вернуть массив answer, такой, что answer [i] равен произведению всех элементов nums кроме nums [i].

Произведение любого префикса или суффикса чисел гарантированно соответствует 32-битному целому числу.

Вы должны написать алгоритм, который работает за O (n) время и без использования операции деления.

Описание проблемы взято из: https://leetcode.com/problems/product-of-array-except-self

Пример 1:

Input: nums = [1, 2, 3, 4] 
Output: [24, 12, 8, 6]

Пример 2:

Input: nums = [-1, 1, 0, -3, 3] 
Output: [0, 0, 9, 0, 0]

Ограничения:

- 2 <= nums.length <= 10^5 - 
-30 <= nums[i] <= 30 
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Последующие действия: Сможете ли вы решить проблему за счет O (1) лишнего пространства? (Выходной массив не считается дополнительным пространством для анализа сложности пространства.)

Объяснение

Подход грубой силы

Согласно постановке задачи, мы не можем использовать оператор деления. Первый подход, который мы можем придумать, - использовать два вложенных цикла for и умножать два числа, когда индексы не совпадают.

Небольшой фрагмент приведенного выше решения на C ++ будет выглядеть, как показано ниже:

vector<int> answer(nums.size(), 0);

for(int i = 0; i < nums.size(); i++){
    product = 1;

    for(int j = 0; j < nums.size(); j++){
        if(i != j){
            product *= nums[j];
        }
    }

    answer[i] = product;
}

Проблема с вышеупомянутым подходом - временная сложность. Временная сложность описанного выше подхода составляет O (N²).

Линейный подход

Мы можем оптимизировать приведенное выше решение до O (N), оценивая произведения элемента слева направо и справа налево.

Давайте проверим алгоритм

- initialize vector<int>answer, i
- set product = 1

- loop for i = 0; i < nums.size(); i++
  - append answer.push_back(product)
  - set product = product * nums[i]

- reset product = 1

- loop for i = nums.size() - 1; i >= 0; i--
  - set answer[i] = answer[i]*product
  - product *= nums[i]

- return answer

Решение C ++

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> answer;
        int product = 1, i;

        for(i = 0; i < nums.size(); i++){
            answer.push_back(product);
            product *= nums[i];
        }

        product = 1;
        for(i = nums.size() - 1; i >= 0; i--){
            answer[i] *= product;
            product *= nums[i];
        }

        return answer;
    }
};

Решение Голанга

func productExceptSelf(nums []int) []int {
    answer := make([]int, len(nums))
    product := 1

    for i := 0; i < len(nums); i++ {
        answer[i] = product
        product *= nums[i]
    }

    product = 1

    for i := len(nums) - 1; i >= 0; i-- {
        answer[i] *= product
        product *= nums[i]
    }

    return answer
}

Решение Javascript

var productExceptSelf = function(nums) {
    var answer = [];
    let product = 1;

    for(let i = 0; i < nums.length; i++){
        answer[i] = product;
        product *= nums[i];
    }

    product = 1;

    for(let i = nums.length - 1; i >= 0; i--){
        answer[i] *= product;
        product *= nums[i];
    }

    return answer;
};

Давайте проверим наш алгоритм, чтобы увидеть, как работает решение.

Input: nums = [1, 2, 3, 4]

Step 1: vector<int> answer
        int product = 1, i

Step 2: loop for i = 0; i < nums.size()
        0 < 4
        true

        answer.push_back(product)
        answer.push_back(1)
        answer = [1]

        product *= nums[i]
        product = product * nums[0]
                = 1 * 1
                = 1

        i++
        i = 1

Step 3: loop for i < nums.size()
        1 < 4
        true

        answer.push_back(product)
        answer.push_back(1)
        answer = [1, 1]

        product *= nums[i]
        product = product * nums[1]
                = 1 * 2
                = 2

        i++
        i = 2

Step 4: loop for i < nums.size()
        2 < 4
        true

        answer.push_back(product)
        answer.push_back(2)
        answer = [1, 1, 2]

        product *= nums[i]
        product = product * nums[2]
                = 2 * 3
                = 6

        i++
        i = 3

Step 5: loop for i < nums.size()
        3 < 4
        true

        answer.push_back(product)
        answer.push_back(6)
        answer = [1, 1, 2, 6]

        product *= nums[i]
        product = product * nums[3]
                = 6 * 4
                = 24

        i++
        i = 4

Step 6: loop for i < nums.size()
        4 < 4
        false

Step 7: product = 1

Step 8: loop for i = nums.size() - 1; i >= 0
        i = 4 - 1 = 3
        i >= 0
        3 >= 0
        true

        answer[i] *= product
                  = answer[3] * product
                  = 6 * 1
                  = 6

        product *= nums[i]
                 = product * nums[3]
                 = 1 * 4
                 = 4

        i--
        i = 2

Step 9: loop for i >= 0
        2 >= 0
        true

        answer[i] *= product
                  = answer[2] * product
                  = 2 * 4
                  = 8

        product *= nums[i]
                 = product * nums[2]
                 = 4 * 3
                 = 12

        i--
        i = 1

Step 10: loop for i >= 0
        1 >= 0
        true

        answer[i] *= product
                  = answer[1] * product
                  = 1 * 12
                  = 12

        product *= nums[i]
                 = product * nums[1]
                 = 12 * 2
                 = 24

        i--
        i = 0

Step 11: loop for i >= 0
        0 >= 0
        true

        answer[i] *= product
                  = answer[0] * product
                  = 1 * 24
                  = 24

        product *= nums[i]
                 = product * nums[0]
                 = 24 * 1
                 = 24

        i--
        i = -1

Step 12: loop for i >= 0
         -1 >= 0
         false

Step 13: return answer

So the answer is [24, 12, 8, 6]

Первоначально опубликовано на https://alkeshghorpade.me.