精选50题之 238. 除自身以外数组的乘积

左手的ㄟ右手 2023-06-06 08:14 20阅读 0赞

### 腾讯精选练习（50 题）之 238. 除自身以外数组的乘积 ###

*   *  原题目链接
     *  直接实现
     *  题目分析
     *  解题分析
     *  代码实现
     *  其他方式
     *  写在最后

## [原题目链接][Link 1] ##

给定长度为 n 的整数数组 `nums`，其中 n > 1，返回输出数组`output`，其中 `output[i]`等于 `nums`中除 `nums[i]`之外其余各元素的乘积。

示例:

输入: [1,2,3,4]
    输出: [24,12,8,6]
    说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶：  
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

## 直接实现 ##

第一个思路是使用除法，虽然题目要求不能使用，still need a try

class Solution {
        
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
        
            int total = 1, n = nums.size(), flag = 0;
            vector<int> res(n, 0);
            for(int i= 0; i < n; i++)
            {
        
                if(nums[i] == 0)
                {
        
                    flag++;
                    break;
                }
                else
                    total *= nums[i];
                if(flag > 1)
                    return res;
            }
            for(int i = 0; i < n; i++)
            {
        
                if(nums[i] == 0)
                {
        
                    res[i] = total;
                    break;
                }
                res[i] = total / nums[i];
            }
            return res;
        }
    };

结果，由于0的出现很不友好，需要加入更多的判定条件去规避特殊情况，作罢。

## 题目分析 ##

就是`output[i]`等于 `nums`中除 `nums[i]`之外其余各元素的乘积

## 解题分析 ##

有一个思路是，把nums\[i\]左侧的元素先相乘，再乘上nums\[i\]右侧的元素，但仔细一想，其实是O(N^2)量级的（两个for循环）。  
在实际实现时，要有改写——通过空间换时间。

## 代码实现 ##

class Solution {
        
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
        
            int n=nums.size();
            vector<int> lAcc(n, 1), rAcc(n, 1); // 左乘积，右乘积
        
            for(int i = 1; i < n; i++)
                lAcc[i] = lAcc[i-1] * nums[i-1];
            
            for(int i = n-2 ;i >= 0; i--)
                rAcc[i] = rAcc[i+1] * nums[i+1];
            
            for(int i = 0; i < n; i++)
                lAcc[i] *= rAcc[i];
    
            return lAcc;
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]  
复杂度分析：

*  时间复杂度：O(N)
 *  空间复杂度：O(N)

## 其他方式 ##

一、  
用双指针标记每个位置的左积(left)和右积(right)，这样在一次遍历中就可以计算出结果。  
eg:\[1,2,3,4,5\]  
2的左积在i=1时就算出，并且会更新此时的左积值。而其右积则在i=3时算出。

class Solution {
        
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
        
            
            int n = nums.size();
            int left=1, right=1;     //left：从左边累乘，right：从右边累乘
            vector<int> res(n,1);
            
            for(int i=0; i<n; i++)    //最终每个元素其左右乘积进行相乘得出结果
            {
        
                res[i] *= left;       //乘以其左边的乘积
                left *= nums[i];
                
                res[n-1-i] *= right;  //乘以其右边的乘积
                right *= nums[n-1-i];
            }
            return res;
        }
    };

[司南牧的回答][Link 2]

class Solution {
        
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
        
        int curAccProduct = 1;
    	vector<int> result;
    	for (int i = 0; i < nums.size(); i++)
    	{
        
    		result.push_back(curAccProduct);
    		curAccProduct *= nums[i];
    	}
    	curAccProduct = 1;
    	for (int i = nums.size()-1; i >= 0; i--)
    	{
        
    		result[i] *= curAccProduct;
    		curAccProduct *= nums[i];
    	}
    	return result;
    	}
    };

## 写在最后 ##

Three Left

[Link 1]: https://leetcode-cn.com/problems/product-of-array-except-self/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTcyODQzMQ_size_16_color_FFFFFF_t_70]: /images/20230601/d934b73acdd749a5b260a92df68404d6.png
[Link 2]: https://leetcode-cn.com/problems/product-of-array-except-self/solution/ji-bai-99de-yong-hu-by-varyshare-2/