可以进阶有点意思-＞给你不一样的体验

238. 除自身以外数组的乘积

难度中等1347

给你一个整数数组 nums返回 数组 answer 其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

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

示例 1:

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

示例 2:

输入: nums = [-1,1,0,-3,3]

输出: [0,0,9,0,0]

提示

• 2 <= nums.length <= 105

• -30 <= nums[i] <= 30

• 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶你可以在 O(1) 的额外空间复杂度内完成这个题目吗 出于对空间复杂度分析的目的输出数组不被视为额外空间。

这道题很有意思 有多种解法

第一眼 有人会说很简单

将所有的元素乘起来 再除以各自的值

但题目让大家失望了 不让用 气人不

第二种 利用循环 计算前后缀 之积

就是将自身值跳过 计算出每个前后缀之积

优点理解方便 思路清晰 缺点时间复杂度有点大 不符合题意循环重复次数太多

//int* productExceptSelf(int* nums, int numsSize, int* returnSize)
//{
//    int sum = 1, a = 0;
//    int* p = (int*)malloc(sizeof(int) * numsSize);
//    if (p == NULL)
//    {
//        printf("error:failed to allocate memory.");
//    }
//    else
//    {
//        for (int i = 0; i < numsSize; i++)
//        {
//            for (int j = 0; j < numsSize; j++)
//            {
//                if (j != i)//跳过他本身
//                {
//                    sum *= nums[j];
//                }
//            }
//            p[a] = sum;
//            a++;
//            sum = 1;
//        }
//        *returnSize = a;
//        return p;
//    }
//}

第三种方法 就是开辟两个数组 一个存放前缀之积 一个存放后缀之积 再将这两个数组的对应位置相乘赋给第三个数组

缺点开辟了三个数组 空间复杂度有点大 你也可以将两个数组各自的乘积赋给他们任意一个 并返回 减少开辟空间

//int* productExceptSelf(int* nums, int numsSize, int* returnSize)
//{
//    //先开辟两个数组 一个存放前缀之积 一个存放后缀之积
//    int* p1 = (int*)malloc(sizeof(int) * numsSize);
//    int* p2 = (int*)malloc(sizeof(int) * numsSize);
//    //由于首元素和尾元素 的前后缀都没有 所以要初始化为一 
//    p1[0] = 1, p2[numsSize-1] = 1;
//    //将前缀之积放于p1 p2为后缀之积
//    int l = 1, r = numsSize - 1;
//    int sum1 = 1, sum2 = 1;
//    for (int i = 1; i < numsSize; i++)
//    {
//        sum1 *= nums[i-1];
//        p1[i] = sum1;
//    }
//    for (int i = numsSize - 1 - 1; i >= 0; i--)
//    {
//        sum2 *= nums[i + 1];
//        p2[i] = sum2;
//    }
//    //在开辟一个数组接受前缀和后缀之积
//    int* p3 = (int*)malloc(sizeof(int) * numsSize);
//    for (int i = 0; i < numsSize; i++)
//    {
//        p3[i] = p1[i] * p2[i];
//    }
//    //free(p1);
//    //p1 = NULL;
//    //free(p2);
//    //p2 = NULL;
//    *returnSize = numsSize;
//    return p3;
//}

有人注意到 题目最下边还有个进阶版本

第四种方法 就是开辟一个数组 用来存放 前缀或者 后缀 用一个变量周转 后缀或者前缀 再将变量乘在开辟的数组对应的项上

有点空间复杂度降低

//int* productExceptSelf(int* nums, int numsSize, int* returnSize)
//{
//    //开辟一个数组用来存储前缀 也可以存储后缀
//    int* p = (int*)malloc(sizeof(int) * numsSize);
//    p[0] = 1;
//    int sum1 = 1;
//    for (int i = 1; i < numsSize; i++)
//    {
//        sum1 *= nums[i - 1];
//        p[i] = sum1;
//    }
//    int sum2 = 1;//因为数组首元素和尾元素 的前后没有元素 所以初始化为1
//    for (int i = numsSize - 1 - 1; i >= 0; i--)//第一个减一是尾元素下标 第二次减一是从倒数第二个元素开始 有题目可知后缀之积 不包括本元素
//    {
//        p[i + 1] *= sum2;
//        sum2 *= nums[i + 1];
//    }
//    //最后一次循环 的后缀之积没有乘在前缀之积上
//    p[0] *= sum2;
//    *returnSize = numsSize;
//    return p;
//}

以上者四种方法 都挺不错的 不同方法适用不同的题目

多加理解 加油~