|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
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
- class Solution(object):
- def productExceptSelf(self, nums):
- """
- :type nums: List[int]
- :rtype: List[int]
- """
- a = 1
- b = 1
- l = len(nums)
- answer = []
- for x in nums:
- answer.append(a)
- a *= x
- for i in range(l-1, -1, -1):
- answer[i] *= b
- b *= nums[i]
- return answer
复制代码
Mike
C++
- vector<int> productExceptSelf(vector<int>& nums) {
- vector<int> result;
- int prod = 1;
- for (auto i : nums) {
- result.push_back(prod);
- prod = i;
- }
- prod = 1;
- for (int i = nums.size() - 1; i >= 0; i--) {
- result[i]= prod;
- prod *= nums[i];
- }
- return result;
- }
复制代码 |
|