LeetCode 238 Product of Array Except Self

标签: 数组类题目 LeetCode 发布于:2022-03-06 10:12:50 编辑于:2022-03-06 10:12:56 浏览量:375

概述

https://leetcode.com/problems/product-of-array-except-self/

要求 O(n) 时间复杂度,不能用除法。

这不是剑指 Offer 上的原题么。

前缀积与后缀积

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> lp = nums, rp = nums;
        for (int i = 1; i < nums.size(); i ++) {
            lp[i] = lp[i-1] * nums[i];
        }
        for (int i = nums.size() - 2; i >= 0; i --) {
            rp[i] = rp[i+1] * nums[i];
        }
        vector<int> ans = nums;
        ans[0] = rp[1];
        ans[ans.size()-1] = lp[ans.size()-2];
        for (int i = 1; i < ans.size() - 1; i ++) {
            ans[i] = lp[i-1] * rp[i+1];
        }
        return ans;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/