数组除自身以外元素的乘积：寻求O(n)时间复杂度解决方案

给定数组：

int arr[]={1,2,3,4}

需要得到结果数组 {24,12,8,6}，即结果数组的每个元素为原数组中除对应索引i外所有元素的乘积（例如索引0对应arr[1]*arr[2]*arr[3]，索引1对应arr[0]*arr[2]*arr[3]）。

当前已有一个时间复杂度为O(n²)的实现：

public int[] calculate(int[] arr){
    int len=arr.length;
    int[] arr1=new int[len];
    for(int i=0;i<len;i++){
        int result=1;
        for(int j=0;j<len;j++){
            if(i!=j){
                result=result*arr[j];
            }
        }
        arr1[i]=result;
    }
    return arr1;
}

O(n)时间复杂度解决方案 #

思路 #

通过两次线性遍历分别计算每个元素的左侧乘积和右侧乘积，最终结果为两者的乘积：

1. 第一次正向遍历，计算每个元素左边所有元素的乘积，存入结果数组
2. 第二次反向遍历，计算每个元素右边所有元素的乘积，同时和结果数组中已存的左侧乘积相乘，得到最终结果

这种方法无需除法（避免数组含0时的异常情况），时间复杂度O(n)，空间优化后可达到O(1)（除结果数组外无额外空间）。

代码实现（空间优化版） #

public int[] calculate(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    
    // 第一步：计算左侧乘积，存入result
    result[0] = 1;
    for (int i = 1; i < len; i++) {
        result[i] = result[i-1] * arr[i-1];
    }
    
    // 第二步：反向遍历计算右侧乘积，并与左侧乘积相乘
    int rightProduct = 1;
    for (int i = len - 1; i >= 0; i--) {
        result[i] = result[i] * rightProduct;
        rightProduct *= arr[i];
    }
    
    return result;
}

代码解释 #

• 正向遍历时，result[i]存储arr[0]到arr[i-1]的乘积
• 反向遍历时，用rightProduct累加右侧元素的乘积，每一步将result[i]（左侧乘积）乘以rightProduct（右侧乘积），得到排除当前元素的总乘积
• 整个过程仅两次线性遍历，时间复杂度O(n)，除结果数组外仅用一个变量，空间复杂度O(1)（忽略结果数组的必要空间）

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