【朱迪的LeetCode刷题笔记】238. Product of Array Except Self #Medium #Python #C++

Judie

Given an integer array nums, return an array answer such that answer<i> is equal to the product of all the elements of nums except nums<i>.

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:
2 <= nums.length <= 105
-30 <= nums<i> <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up:
Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Judy
Python

1. class Solution(object):
   
2.     def productExceptSelf(self, nums):
   
3.         """
   
4.         :type nums: List[int]
   
5.         :rtype: List[int]
   
6.         """
   
7.         a = 1
   
8.         b = 1
   
9.         l = len(nums)
   
10.         answer = []
    
11.         for x in nums:
    
12.             answer.append(a)
    
13.             a *= x
    
14.         for i in range(l-1, -1, -1):
    
15.             answer[i] *= b
    
16.             b *= nums[i]
    
17.         return answer
    

复制代码

Mike
C++

1. vector<int> productExceptSelf(vector<int>& nums) {
   
2.         vector<int> result;
   
3.         int prod = 1;
   
4.         for (auto i : nums) {
   
5.             result.push_back(prod);
   
6.             prod = i;
   
7.         }
   
8.         prod = 1;
   
9.         for (int i = nums.size() - 1; i >= 0; i--) {
   
10.             result[i]= prod;
    
11.             prod *= nums[i];
    
12.         }
    
13.         return result;
    
14.     }
    

复制代码