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.)
1 #include<stdio.h> 2 3 /** 4 * Return an array of size *returnSize. 5 * Note: The returned array must be malloced, assume caller calls free(). 6 */ 7 int* productExceptSelf(int* nums, int numsSize, int* returnSize) 8 { 9 if( numsSize == 0 ) 10 { 11 return 0; 12 } 13 14 int *result = malloc(numsSize*sizeof(int)); 15 *returnSize = numsSize; 16 17 /* 从左往右 */ 18 int i; 19 int leftProduct = 1; 20 int rightProduct = 1; 21 22 for( i=0; i<numsSize; i++ ){ 23 result[i] = leftProduct; 24 leftProduct *= nums[i]; 25 } 26 /* 从右往左 */ 27 for( i = numsSize - 1; i>=0; i-- ){ 28 result[i] *= rightProduct; 29 rightProduct *= nums[i]; 30 } 31 32 return result; 33 } 34 35 int main(){ 36 37 int nums[] = {1,2,3,4,5,6,7}; 38 int numsSize = 7; 39 int returnSize[numsSize]; 40 productExceptSelf( nums, numsSize, returnSize); 41 return 0; 42 }
原文：http://www.cnblogs.com/Juntaran/p/5444968.html