238.除了自Leetcode之外的数组的乘积

Question

我一直在leetcode上尝试这个问题。238.除自身之外的数组的乘积

给定一个整数数组nums，返回一个数组answer，使得 answer[i]等于nums中除nums[i]之外 的所有元素的乘积。

nums 的任何前缀或后缀的乘积保证适合 32 位整数。

您必须编写一个在O(n)时间内运行且不使用除法运算的算法。

示例1：

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

Output: [24,12,8,6]

示例2：

Input: nums = [-1,1,0,-3,3]
 
 Output: [0,0,9,0,0]

这是我对上述问题的解决方案。

public int[] productExceptSelf(int[] nums) {
   
    int answer[]=new int[nums.length];
    for(int i=0;i<nums.length;i++){
        int prod=1;
        for(int j=0;j<nums.length;j++){
            if(j!=i)
                
                prod=prod*nums[j];
        }
        answer[i]=prod;
    }
    return answer;
}

这正在通过 19/20 测试用例。有一个测试用例不起作用，并且我收到错误“超出时间限制”。

失败的测试用例如下：

Input: [-1,-1,-1,-1,..............];
 
Output: Time limit exceeded.

如果有人可以帮助我，我必须对我的代码执行什么版本？

Answer 1

我也做leetcode，它给你TLE，因为这不是他们期望的解决方案。它是正确的，但需要 O(N*N) 次运算来计算，有更好的 O(N) 解决方案，

public int[] productExceptSelf(int[] nums) {
          
        int output[] = new int[ nums.length];
        
        output[0] = 1;

        // left prefix product
        for(int i=1;i<nums.length;i++){
             output[i] = output[i-1] * nums[i-1];
        }
        
        int product = 1;

        for(int i=nums.length-1;i>=0;i--){
            
            output[i] = output[i] * product;
            
            product*= nums[i];
        }
        
        return output;
}