Product of Array Except Self
Given an array of n integers where n > 1, nums,
return an array output such that output[i] is equal to the product
of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity?
(Note: The output array does not count as extra space
for the purpose of space complexity analysis.)
/*************************************************************************
> File Name: LeetCode238.c
> Author: Juntaran
> Mail: Jacinthmail@gmail.com
> Created Time: 2016年04月28日 星期四 23时40分01秒
************************************************************************/ /************************************************************************* Product of Array Except Self Given an array of n integers where n > 1, nums,
return an array output such that output[i] is equal to the product
of all the elements of nums except nums[i]. Solve it without division and in O(n). For example, given [1,2,3,4], return [24,12,8,6]. Follow up:
Could you solve it with constant space complexity?
(Note: The output array does not count as extra space
for the purpose of space complexity analysis.) ************************************************************************/ #include<stdio.h> /**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
if( numsSize == )
{
return ;
} int *result = malloc(numsSize*sizeof(int));
*returnSize = numsSize; /* 从左往右 */
int i;
int leftProduct = ;
int rightProduct = ; for( i=; i<numsSize; i++ ){
result[i] = leftProduct;
leftProduct *= nums[i];
}
/* 从右往左 */
for( i = numsSize - ; i>=; i-- ){
result[i] *= rightProduct;
rightProduct *= nums[i];
} return result;
} int main(){ int nums[] = {,,,,,,};
int numsSize = ;
int returnSize[numsSize];
productExceptSelf( nums, numsSize, returnSize);
return ;
}