In this Leetcode Product of Array Except Self problem solution we have 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.
Problem solution in Python.
class Solution(object): def productExceptSelf(self, nums): """ :type nums: List[int] :rtype: List[int] """ left = [1] * len(nums) right = [1] * len(nums) res = [] for i in range (1, len(nums)): left[i] = left[i-1] * nums[i-1] for i in range (len(nums)-2, -1, -1): right[i] = right[i+1] * nums[i+1] for i in range (0, len(nums)): res.append(left[i] * right[i]) return res
Problem solution in Java.
class Solution { public int[] productExceptSelf(int[] nums) { int tmp = 1; int n =nums.length; int[] left = new int[nums.length]; int[] right = new int[n]; left[0] = 1; for (int i = 1; i < n; i++){ tmp *= nums[i-1]; left[i] = tmp; } right[n-1] = 1; tmp = 1; for (int i = n - 2; i >= 0; i--){ tmp *= nums[i+1]; right[i] = tmp; } for (int i = 0; i < n; i++){ nums[i] = left[i] * right[i]; } return nums; } }
Problem solution in C++.
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int cnt=0; int n=nums.size(); vector<int>pref(n),suf(n); for(int i=0;i<n;i++){ pref[i]=nums[i]; if(i) pref[i]*=pref[i-1]; } for(int i=n-1;~i;i--){ suf[i]=nums[i]; if(i<n-1) suf[i]*=suf[i+1]; } for(int i=0;i<n;i++){ if(i==0){ nums[i]=suf[i+1]; }else if(i==n-1){ nums[i]=pref[i-1]; }else{ nums[i]=(pref[i-1]*suf[i+1]); } } return nums; } };
Problem solution in C.
int* productExceptSelf(int* nums, int numsSize, int* returnSize) { int sum = 1; int flag = 0; for (int i = 0; i < numsSize && flag < 2; i++){ if (!nums[i]) {flag++; continue;} sum = sum * nums[i]; } int* result = (int*)malloc(sizeof(int) * numsSize); memset(result, 0, sizeof(int)*numsSize); *returnSize = numsSize; if (flag>1) return result; for (int i = 0; i < numsSize; i++){ if (!nums[i]) {result[i] = sum; continue;} if (flag > 0) {result[i] = 0; continue;} result[i] = sum / nums[i]; } return result; }
0 Comments