讨论/《算法面试题汇总》 - 除自身以外数组的乘积/
《算法面试题汇总》 - 除自身以外数组的乘积
共 3 个回复

看题啊喂
说明: 请不要使用除法,且在 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;
	}
};

卡了乘法的一个性质

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;
    }
};