Leetcode 238 Product of Array Except Self 时间O(n)和空间O(1)解法

全栈程序员站长

发布于 2022-07-08 21:17:58

26500

代码可运行

文章被收录于专栏：全栈程序员必看全栈程序员必看

运行总次数：0

代码可运行

大家好，又见面了，我是全栈君。

1. 问题描写叙述

　　给定一个n个整数的数组（ n>1 )nums，返回一个数组output，当中的元素 outputi 的值为原数组nums中除 numsi 之外的全部元素的积。比如：nums数组为[1,2,3,4]。返回的output数组为[24,12,8,6]。

　　要求不用除法和时间复杂度为O(n).

2. 方法与思路

　　这道题假设没有除法的限制的话就非常easy了，先求全部数的乘积，然后除以 numsi 。考虑一下除数为零的情况，非常好解决。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> re;
        long mul=1;
        int zeroNum = 0;

        for(int i=0; i < nums.size(); i++)
        {
            if(nums[i] != 0) mul *= nums[i];
            else zeroNum++;
        }

        for(int i = 0; i < nums.size(); i++)
        {
            if(zeroNum > 1) re.push_back(0);
            else if(zeroNum == 1)
            {
                if(nums[i] == 0) re.push_back(mul);
                else re.push_back(0);
            }
            else 
                re.push_back(mul/nums[i]);
        }
        return re;
    }
};

　　可是题目上明白要求不能用除法，那我们得另辟蹊径了。以下以数组[1,2,3,4,5]为例，看完以下表述就明白了：

扫描顺序	1	2	3	4	5
从左至右	1	1×1	1×1×2	1×1×2×3	1×1×2×3×4
从右至左	1×(2×3×4×5)	(1×1）×(3×4×5)	(1×1×2)×(4×5)	(1×1×2×3)×(5)	(1×1×2×3×4)×(1)

　　就是先从左至右扫描，记录前 i−1 个数的乘积，第二遍扫描时，从右至左。将乘积再乘以后 i+1 位的乘积。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> re(nums.size(),1);
        int i,tmp = 1;

        for(i = 1; i < nums.size(); i++)
            re[i] =re[i-1] * nums[i-1];

        for(i = nums.size()-1; i >= 0; i--)
            re[i] *= tmp,tmp *= nums[i];

        return re;
    }
};

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/115781.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年1月3，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法