leetcode238：除自身以外数组的乘积

题目链接

leetcode

题目描述

一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
不使用 除法，且在 O(n) 时间复杂度内完成此题。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

void printArray(const vector<int>& nums) {
    cout << "[";
    for (const int& num : nums) {
        cout << num << ",";
    }
    cout << "]" << endl;
}

/*
    注意：输入数组中出现 0，并且不允许使用除法运算，增加了难度。
    
    左右乘积列表
    不需要将所有数字的乘积除以给定索引处的数字得到相应的答案，
    而是使用索引左侧所有数字的乘积和右侧所有数字的乘积（即，前缀与后缀）相乘得到答案。
    
    时间复杂度：O(n)
        其中 n 指的是数组的大小。
        预处理 left 和 right 数组以及遍历计算结果的时间复杂度都是 O(n) 。
    空间复杂度：O(n)
        left 和 right 数组的大小。
*/
class Solution_0 {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, 0), right(n, 0); // left 和 right 分别表示左右两侧的乘积列表
        vector<int> res(n);

        // left[i] 表示索引 i 左侧所有元素的乘积
        left[0] = 1;
        for (int i = 1; i < n; i ++) {
            left[i] = nums[i - 1] * left[i - 1];
        }
        // right[i] 表示索引 i 右侧所有元素的乘积
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i --) {
            right[i] = nums[i + 1] * right[i + 1];
        }
        // 计算结果
        for (int i = 0; i < n; i ++) {
            res[i] = left[i] * right[i];
        }

        return res;
    }
};

/*
    由于输出数组不算在空间复杂度内，所以将 L 或 R 使用输出数组来计算。
    先把输出数组当作 L 数组来计算，再动态构造 R 数组得到结果。
    
    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);

        // res[i] 表示索引 i 左侧所有元素的乘积
        res[0] = 1;
        for (int i = 1; i < n; i ++) {
            res[i] = nums[i - 1] * res[i - 1];
        }

        // R 表示右侧所有元素的乘积
        int R = 1;
        for (int i = n - 1; i >= 0; i --) {
            res[i] = res[i] * R;
            R = R * nums[i];
        }

        return res;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> nums = {
        {1,2,3,4},
        {-1,1,0,-3,3}
    };

    for (auto& num : nums) {
        cout << "Input: ";
        printArray(num);
        vector<int> result = solution.productExceptSelf(num);
        cout << "Output: ";
        printArray(result);
    }

    return 0;
}

Golang 代码

package main

import "fmt"

/*
   基本思路：
       1.创建一个与输入数组长度相同的结果数组 result，并初始化为全 1。
       2.从左到右遍历数组，计算每个位置左边所有元素的乘积，并累乘到 result[i]。
       3.从右到左遍历数组，计算每个位置右边所有元素的乘积，并累乘到 result[i]。
       4.返回结果数组 result。

   时间复杂度：O(n)
       其中 n 是数组的长度，需要遍历数组两次。
   空间复杂度：O(1)
       创建了一个与输入数组长度相同的输出数组，已知输出数组不视为额外空间。
*/
func productExceptSelf(nums []int) []int {
    n := len(nums)
    res := make([]int, n)

    // 计算左边的乘积
    leftProduct := 1
    for i := 0; i < n; i ++ {
        res[i] = leftProduct
        leftProduct *= nums[i]
    }
    // 计算右边的乘积
    rightProduct := 1
    for i := n - 1; i >= 0; i -- {
        res[i] *= rightProduct
        rightProduct *= nums[i]
    }

    return res
}

func main() {
    // 测试用例
    testCases := []struct {
        nums     []int
        expected []int
    }{
        {[]int{1,2,3,4}, []int{24,12,8,6}},
        {[]int{-1,1,0,-3,3}, []int{0,0,9,0,0}},
    }
    
    for i, tc := range testCases {
        fmt.Printf("Test Case %d, Input: nums = %v\n", i+1, tc.nums)
        result := productExceptSelf(tc.nums)
        resultStr := fmt.Sprintf("%v", result)
        expectedStr := fmt.Sprintf("%v", tc.expected)

        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
    }
}