剑指 Offer 66 构建乘积数组

    
        标签：
        
            剑指 Offer
        
    发布于：2022-02-28 11:03:21
    编辑于：2022-02-28 11:04:11
    浏览量：941

概述

https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/

不能使用除法。

暴力解

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        vector<int> ans = a;
        for (int i = 0; i < a.size(); i ++) {
            ans[i] = 1;
            for (int j = 0; j < a.size(); j ++) {
                if (i != j) ans[i] *= a[j];
            }
        }
        return ans;
    }
};

O(n^2) 时间复杂度。

TLE 了。

前缀积和后缀积

O(n) 的时间复杂度。

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        vector<int> pre = a;
        vector<int> post = a;
        for (int i = 1; i < a.size(); i ++) {
            pre[i] = pre[i-1] * a[i];
        }
        for (int i = a.size() - 2; i >= 0; i --) {
            post[i] = post[i+1] * a[i];
        }
        vector<int> ans = a;
        for (int i = 0; i < a.size(); i ++) {
            int preProduct = 1;
            if (i != 0) preProduct = pre[i-1];
            int postProduct = 1;
            if (i != a.size() - 1) postProduct = post[i+1];
            ans[i] = preProduct * postProduct;
        }
        return ans;
    }
};

Links: sword-offer-66