238. Product of Array Except Self

leetcode medium

#array#bit-manipulation#csharp#leetcode#medium#prefix-sum

Task

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

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

C# solution

matched/original

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int length = nums.Length;
        int[] L = new int[length];
        int[] R = new int[length];
        int[] answer = new int[length];
        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }
        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }
        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }
        return answer;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& ProductExceptSelf(vector<int>& nums) {
        int length = nums.size();
        vector<int>& L = new int[length];
        vector<int>& R = new int[length];
        vector<int>& answer = new int[length];
        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }
        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }
        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }
        return answer;
    }
}

Java solution

matched/original

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] L = new int[length];
        int[] R = new int[length];
        int[] answer = new int[length];

        L[0] = 1;
        for (int i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }

        R[length - 1] = 1;
        for (int i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }

        for (int i = 0; i < length; i++) {
            answer[i] = L[i] * R[i];
        }

        return answer;
    }
}

JavaScript solution

matched/original

class Solution {
    productExceptSelf(nums) {
        const length = nums.length
        const L = new Array(length).fill(1)
        const R = new Array(length).fill(1)
        const answer = new Array(length).fill(1)

        for (let i = 1; i < length; i++) {
            L[i] = nums[i - 1] * L[i - 1]
        }

        for (let i = length - 2; i >= 0; i--) {
            R[i] = nums[i + 1] * R[i + 1]
        }

        for (let i = 0; i < length; i++) {
            answer[i] = L[i] * R[i]
        }

        return answer
    }
}

Python solution

matched/original

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        length = len(nums)
        L = [1] * length
        R = [1] * length
        answer = [1] * length

        for i in range(1, length):
            L[i] = nums[i - 1] * L[i - 1]

        for i in range(length - 2, -1, -1):
            R[i] = nums[i + 1] * R[i + 1]

        for i in range(length):
            answer[i] = L[i] * R[i]

        return answer

Go solution

matched/original

func productExceptSelf(nums []int) []int {
    length := len(nums)
    L := make([]int, length)
    R := make([]int, length)
    answer := make([]int, length)

    L[0] = 1
    for i := 1; i < length; i++ {
        L[i] = nums[i-1] * L[i-1]
    }

    R[length-1] = 1
    for i := length - 2; i >= 0; i-- {
        R[i] = nums[i+1] * R[i+1]
    }

    for i := 0; i < length; i++ {
        answer[i] = L[i] * R[i]
    }

    return answer
}

Explanation

Algorithm

Пример

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

Output: [24,12,8,6]

👨‍💻

Алгоритм:

Инициализация массивов L и R: Инициализируйте два пустых массива L и R. Массив L будет содержать произведение всех чисел слева от i, а массив R будет содержать произведение всех чисел справа от i. Заполните массив L, установив L[0] равным 1, а для остальных элементов используйте формулу L[i] = L[i-1] * nums[i-1]. Заполните массив R, установив R[length-1] равным 1, а для остальных элементов используйте формулу R[i] = R[i+1] * nums[i+1].

Заполнение массивов L и R: Пройдите два цикла для заполнения массивов L и R. В первом цикле заполните массив L, начиная с L[0] и двигаясь вправо. Во втором цикле заполните массив R, начиная с R[length-1] и двигаясь влево.

Формирование результата: Пройдите по исходному массиву и для каждого элемента i вычислите произведение всех элементов, кроме nums[i], используя L[i] * R[i]. Сохраните результат в массиве answer и верните его.

😎