[数据结构与算法]除自身以外数组的乘积

1.规则：用一个数组储存某个数组中除自身以外的乘积，例：给定数组arr[]={1,2,3,4,5};储存数组str[]={120,60,40,30,24};不可使用除法，当数组中只存在一个元素时，数组乘积默认为1。

2.除法思路：将数组中所有元素相乘在除以其自身某个元素求解

3.前缀思路：以某个元素为中心，可将数组分为左前缀与右前缀两边，将左前缀与右前缀相乘便是除自身以外数组的乘积，当元素为首元素时，左前缀并不存在其成员，为了防止计算出现问题可将最左成员与最右成员添加为1，乘积乘1并不会影响其值，可放心添加。

4.实现除自身以外数组的乘积

//除自身以外数组的乘积
#include<stdio.h>
int* My_lin(int arr[], int sz)
{
    int* lin = (int*)malloc(sz * sizeof(int));
    int left = 1, right = 1;
    for (int i = 0; i < sz; i++) {
        lin[i] = left;
        left *= arr[i];//左前缀之积
    }
    for (int i = sz - 1; i >= 0; i--) {
        lin[i] *= right;//乘积之和
        right *= arr[i];//右前缀之积
    }
    return lin;
}
int main()
{
    int arr[] = { 1,2,3,4,5 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    int* str=My_lin(arr, sz);
    for (int i = 0; i < sz; i++){
        printf("%d ", str[i]);
    }
    return 0;
}