LeetCode-07-元素之积

发表于 更新于 阅读次数： 本文字数： 801 阅读时长 ≈ 3 分钟

LeetCode算法题：元素之积。

题目

LeetCode：LeetCode 75 - 学习计划-07-数组元素除去自身外的乘积

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

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

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

进阶： O(1) 的额外空间复杂度？

思路

最简易的想法是循环计算所有元素的乘积，随后除去元素自身。

在限制除法后将整个乘积过程拆分为两个：

  • 元素左侧的数值之积
  • 元素右侧的数值之积

问题即演变为如何最大程度的减小空间复杂度。

  1. 采用长缓存数组L、R分别存储元素左侧右侧之积，空间复杂度O(2n)
  2. 双循环。anwser [i] = anwser[i-1]*nums[i]，将计算结果直接存入anwser数组内，额外使用int变量存储右侧之积，空间复杂度O(1)。
  3. 单循环。初始化输出数组为全1，额外使用两个int变量L、R存储左右之积，从两侧开始相乘。

代码

方案A-LR数组

LR数组分别计算并存入新数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int* productExceptSelf(int* nums, int numSize, int* returnSize) {
    *returnSize = numSize;
     int *answer = (int *)malloc(sizeof(int)*numSize);
     int *L = (int *)malloc(sizeof(int)*numSize);
     int *R = (int *)malloc(sizeof(int)*numSize);
     L[0] = 1;
     R[numSize - 1] =1;
     for(int i=1; i<numSize; i++)
     {
        L[i] = L[i-1]*nums[i-1];
        R[numSize-i-1] = R[numSize - i] * nums[numSize - i];
     }
    for(int i = 0; i<numSize; i++)
    {
        answer[i] = L[i] * R[i];
    }

    free(L);
    free(R);
        
    return answer;
}

方案B-双循环

  • 首次循环计算元素左侧之积并填入answer
  • 二次循环计算元素右侧之积suffix，并计算新answer
image can't load. 单循环O(1) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int* productExceptSelf(int* nums, int numSize, int* returnSize) {
    *returnSize = numSize;
     int *answer = (int *)malloc(sizeof(int)*numSize);
    answer[0] = 1;
    int suffix = 1; //右侧之积
 
    //正向，元素左侧之积存入answer中
    for(int i=1; i<numSize; i++)
    {
        answer[i] = answer[i-1]*nums[i-1];
    }
	//反向，乘右侧之积suffix，并刷新新值    
    for(int i=1; i<=numSize; i++)
    {
		answer[numSize-i] *= suffix;
        suffix *= nums[numSize-i];
    }
        
    return answer;
}

方案C-单循环

既然方案B中本身两次循环进行双向计算，故可进一步优化为单循环内从左至右计算两次：

  • 使用L、R存储某元素两侧的数值之积，L从左侧计算，R从右侧计算。
  • answer[i]与answer[n-i-1]正向反向两次计算，则单次循环内实现对数据的两次乘积
image can't load. 单循环O(1) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    *returnSize = numSize;
     int *answer = (int *)malloc(sizeof(int)*numSize);
     for(int i=0; i< numSize; i++)
     {
         answer[i] = 1;
     }
     int L = 1, R= 1;
    for(int i=1; i<numSize; i++)
    {
        L *= nums[i - 1];
        R *= nums[n - i];
        
        answer[i] *= L;
        answer[n-i-1] *= R;
    }
    return answer;
}

————————— End —————————

云中谁寄锦书来，雁字回时，月满西楼。–《一剪梅·红藕香残玉簟秋》