讨论/《算法面试题汇总》 - 除自身以外数组的乘积/
《算法面试题汇总》 - 除自身以外数组的乘积
共 4 个回复
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int l=1,r=1;
        vector<int> vl,vr;
        //两个数组一个从前往后一个从后往前计数
        vector<int> ans;
        for(int i=0;i<nums.size();i++)
        {
            vl.push_back(l);
            vr.push_back(r);
            l*=nums[i];
            r*=nums[nums.size()-1-i];
        }
        for(int i=0;i<nums.size();i++)
        {
            ans.push_back(vl[i]*vr[nums.size()-i-1]);
        }
        return ans;
    }
};
1

下面这种解法参考了用户:salt_emperor c++的处理方式,采用双向处理的方法,将时间复杂度降低至 O(n), 额外的增加的空间为 O(2n),所以空间复杂度为 O(n);

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int length = nums.length;
        int[] output = new int[length];


        int[] temp1 = new int[length];
        int[] temp2 = new int[length];

        

        //计算前 i 个数乘积
        temp1[0] = nums[0];
        for (int i= 1; i < length; i ++) {
            temp1[i] = nums[i] * temp1[i - 1];
            //System.out.println(temp1[i]);
        }


        //计算后 length - i - 1 个数的乘积
        temp2[length - 1] = nums[length - 1];
        for (int i = length - 2; i >= 0; i--) {
            temp2[i] = temp2[i + 1] * nums[i];
        }


        output[0] = temp2[1];
        for (int i = 1; i < length - 1; i++) {
            output[i] = temp1[i - 1] * temp2[i + 1];
        } 
        output[length - 1] = temp1[length - 2];

        return output;       
    }
}

看题啊喂
说明: 请不要使用除法,且在 O(n) 时间复杂度内完成此题。

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

class Solution
{
public:
	vector<int> productExceptSelf(vector<int> &nums)
	{
		vector<int> product(nums.size(), 0);
		int all = 1;
		int zeroIndex = -1;

		for (int i = 0; i < nums.size(); i++)
		{
			int num = nums[i];
			if (num != 0)
			{
				all *= num;
			}
			else if (zeroIndex >= 0)
			{
				return product;
			}
			else
			{
				zeroIndex = i;
			}
		}
		if (zeroIndex >= 0)
		{
			product[zeroIndex] = all;
			return product;
		}

		for (int i = 0; i < nums.size(); i++)
		{
			product[i] = all / nums[i];
		}

		return product;
	}
};

卡了乘法的一个性质