Leetcode:238. Product of Array Except Self除自身以外数组的乘积(C语言)

逃离我推掉我的手 2023-06-21 10:27 31阅读 0赞

**问题描述：**  
给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output\[i\] 等于 nums 中除 nums\[i\] 之外其余各元素的乘积。

示例:

输入: \[1,2,3,4\]  
输出: \[24,12,8,6\]

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶：  
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/product-of-array-except-self  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。  
**解答：**

/** * Note: The returned array must be malloced, assume caller calls free(). */
    int* productExceptSelf(int* nums, int numsSize, int* returnSize)
    { 
        int len = 0;
        int i  = 0;
        int j = 0;
        int temp = 1;
    
        len = numsSize;
    
        int *left = (int *)malloc(len * sizeof(int));
        memset(left, 0, len);
    
        int *right = (int *)malloc(len * sizeof(int));
        memset(right, 0, len);
    
        int *output = (int *)malloc(len * sizeof(int));
        memset(output, 0, len);
    
        *returnSize = len;
    
        for(i = 0; i<len; i++)
        { 
            left[i] = temp;
            temp = temp * nums[i];
        }
    
        temp = 1;
        for(i = len - 1; i>=0; i--)
        { 
            right[i] = temp;
            temp = temp * nums[i];
        }
    
        for(i = 0;i<len;i++)
        { 
            output[i] = left[i] * right[i];
        }
    
        free(left);
        free(right);
        return output;
    }

**运行结果：**  
![在这里插入图片描述][2019121214365338.png]  
**Notes：**  
下面的代码是我最开始编写的代码，思路是用两个for循环，第二个for循环中若i==j则不进行乘积运算 这样的话就不会对自身相乘，但是提交的时候显示为时间超限，所以参考别人的解题方法：

int* productExceptSelf(int* nums, int numsSize, int* returnSize)
    { 
        int len = 0;
        int i  = 0;
        int j = 0;
        len = numsSize;
        int temp = 1;
    
        int *sendoutput = (int *)malloc(len * sizeof(int));
        memset(sendoutput, 0, len);
    
        *returnSize = len;
    
        for(i = 0; i<len; i++)
        { 
            for(j = 0; j<len;j++)
            { 
                if(i != j)
                { 
                    temp = nums[j]*temp;
                }
                
            }
            sendoutput[i] = temp;
            temp = 1;
        }
    
        return sendoutput;

[2019121214365338.png]: https://img-blog.csdnimg.cn/2019121214365338.png