LintCode 50: Product of Array Exclude Itself (数组累积经典题)

    xiaoxiao2022-07-12  139

    Product of Array Exclude Itself 中文English Given an integers array A.

    Define B[i] = A[0] * … * A[i-1] * A[i+1] * … * A[n-1], calculate B WITHOUT divide operation.Out put B

    Example Example 1

    Input: A = [1, 2, 3] Output: [6, 3, 2] Explanation:B[0] = A[1] * A[2] = 6; B[1] = A[0] * A[2] = 3; B[2] = A[0] * A[1] = 2 Example 2

    Input: A = [2, 4, 6] Output: [24, 12, 8]

    解法1:用两个累积数组,一前一后。 代码如下:

    class Solution { public: /* * @param nums: Given an integers array A * @return: A long long array B and B[i]= A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1] */ vector<long long> productExcludeItself(vector<int> &nums) { int N = nums.size(); if (N == 0) return vector<long long>(); if (N == 1) return vector<long long>(1, 1); vector<long long> result(N, 0); vector<long long> fromBeginArr(N, 1); long long fromBeginProd = 1; for (int i = 0; i < N; ++i) { fromBeginProd *= nums[i]; fromBeginArr[i] = fromBeginProd; } vector<long long> fromEndArr(N, 1); long long fromEndProd = 1; for (int i = 0; i < N; ++i) { fromEndProd *= nums[N - i - 1]; fromEndArr[i] = fromEndProd; } result[0] = fromEndArr[N - 2]; result[N - 1] = fromBeginArr[N - 2]; for (int i = 1; i < N - 1; ++i) { result[i] = fromBeginArr[i - 1] * fromEndArr[N - 2 - i]; } return result; } };
    最新回复(0)