如何在O(n)复杂度且不使用除法的前提下实现两个嵌套数组对应相乘？

核心思路 #

• 逐对处理两个输入数组的同索引子数组，分别计算每个子数组内部所有元素的乘积，再将两个乘积相乘，作为结果数组对应位置的值
• 设所有子数组的元素总个数为n，方案仅遍历所有元素1次，时间复杂度为O(n)，全程未使用除法运算符，完全符合题目要求

实现示例 #

Python 实现 #

def calculate_nested_product(arr1, arr2):
    result = []
    for sub_arr1, sub_arr2 in zip(arr1, arr2):
        product1 = 1
        for num in sub_arr1:
            product1 *= num
        product2 = 1
        for num in sub_arr2:
            product2 *= num
        result.append(product1 * product2)
    return result

# 测试用例
arr1 = [[1], [1], [1, 2], [1, 2, 3]]
arr2 = [[2, 3, 4], [3, 4], [4], [1]]
print(calculate_nested_product(arr1, arr2)) # 输出：[24, 12, 8, 6]

JavaScript 实现 #

function calculateNestedProduct(arr1, arr2) {
    const result = []
    for(let i = 0; i < arr1.length; i++) {
        let p1 = 1, p2 = 1
        arr1[i].forEach(num => p1 *= num)
        arr2[i].forEach(num => p2 *= num)
        result.push(p1 * p2)
    }
    return result
}

// 测试用例
const arr1 = [[1], [1], [1, 2], [1, 2, 3]]
const arr2 = [[2, 3, 4], [3, 4], [4], [1]]
console.log(calculateNestedProduct(arr1, arr2)) // 输出：[24, 12, 8, 6]

可选优化思路 #

• 如果业务场景中存在大量重复的子数组，可以新增哈希缓存存储已经计算过的子数组的乘积，遇到相同子数组时直接取缓存值，不需要重复计算，可以进一步降低实际运行耗时，时间复杂度依然保持O(n)。

内容的提问来源于stack exchange，提问作者heapnoob