【C语言】每日一题（除自身以外数组的乘积）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C语言】每日一题（除自身以外数组的乘积）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

添加链接描述，链接奉上
【C语言】每日一题（除自身以外数组的乘积）,c语言,算法

暴力循环:

暴力循换真的是差生法宝，简单好懂，就是不实用，大多数的题目都会超过时间限制（无奈）

思路：

1.写一个除自身的数组乘积函数
2.利用for循环遍历数组，i作为循环变量，当遍历到i时，就求出除i以外的数组乘积
3.放入返回数组中

代码实现：

static int arr[100000];
 int mul_self(int* nums, int numsSize,int i)
 //编写一个除自身的数组乘积函数
 {
    int mul=1;
    for(int j=0;j<numsSize;j++)
    {
        if(j!=i)
        mul*=nums[j];
    }
    return mul;
 }
int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{
    *returnSize=numsSize;
    int n=0;
    for(int i=0;i<numsSize;i++)
    //循环遍历，求出每个除i外数组的乘积
    {
        arr[n++]=mul_self(nums,numsSize,i);
    }
    return arr;
}

但是此方法局限大，时间超出限制。

前缀积×后缀积（分组）:

思路：

根据题目提示，利用前缀积×后缀积即可得到答案，那么问题就演化为求前缀积与后缀积
创建两个数组，一个用来存放前缀积，另一个存放后缀积。
最后循环，将两者相乘，得到除了nums[i]外的数组乘积

【C语言】每日一题（除自身以外数组的乘积）,c语言,算法

代码实现：

static int ans[100000];

int* productExceptSelf(int* nums, int numsSize, int* returnSize)
{

    int lsum[numsSize];//创建数组
    int rsum[numsSize];
    lsum[0]=1;//将边界赋值为1
    rsum[numsSize-1]=1;
    for(int i = 1;i < numsSize; i++)//求前缀积
    {
        lsum[i]=lsum[i-1]*nums[i-1];
    }
    for(int i = numsSize-2;i >= 0;i--)//求后缀积
    {
        rsum[i]=rsum[i+1]*nums[i+1];
    }
    for(int i = 0;i<numsSize;i++)//求结果数组
    {
        ans[i]=lsum[i]*rsum[i];
    }
    *returnSize=numsSize;
    return ans;
   
}