Python算法题集_除自身以外数组的乘积_除自身以外数组的乘积算法题

本文为Python算法题集之一的代码示例

题239：除自身以外数组的乘积

1. 示例说明

  给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
  题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
  请 不要使用除法， 且在 O(*n*) 时间复杂度内完成此题。

示例 1:

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

示例 2:

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

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
• 进阶： 你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

---

2. 题目解析

- 题意分解

1. 本题为求所有子数组的乘积
2. 本题的主要计算有2处，1是子数组遍历，2是子数组求乘积
3. 基本的办法是双层循环，挨个计算，所以基本的时间算法复杂度为O(n2）

- 优化思路

1. 减少循环层次

2. 增加分支，减少计算集

3. 采用内置算法来提升计算速度

4. 分析题目特点，分析最优解

   1）采用字典存储数组中每个数字的数量，可以加快子数组求乘积的速度

   2）将字典中每个数字的乘积、少乘一次的乘积先计算出来，改计算为字典查询，可以加快子数组求乘积的速度

   3）采用类似前缀和的思路，计算前缀乘积、后缀乘积，这样第i个元素的除自身外数组的乘积=前缀乘积i-1 * 后缀乘积i+1，可以减少循环层次

   4）进阶算法要求少用临时空间，使用结果数组和原始数组，可以配合完成结果计算

---

- 测量工具

• 本地化测试说明：LeetCode网站测试运行时数据波动很大，因此需要本地化测试解决这个问题
• CheckFuncPerf（函数用时和内存占用测试模块）已上传到CSDN，地址在这里：Python算法题集_检测函数用时和内存占用的模块
• 测试的超时测试用例文件是官网的，已上传到CSDN，地址在这里：力扣算法题：除自身以外数组的乘积，测试超时数组，长度5W

---

3. 代码展开

1) 标准求解【暴力求解】

双层循环，超时未过

import CheckFuncPerf as cfp

def productExceptSelf_base(nums):
 result = []
 for iIdx in range(len(nums)):
     imulti = 1
     for jIdx in range(len(nums)):
         if jIdx!= iIdx:
             imulti *= nums[jIdx]
     result.append(imulti)
 return result

testcase_big = open(r'testcase/hot16_big.txt', mode='r', encoding='utf-8').read().replace('[', '').replace(']', '')
testcase_big = testcase_big.split(',')
nums = [int(x) for x in testcase_big]
result = cfp.getTimeMemoryStr(productExceptSelf_ext1, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))

# 运行结果
函数 productExceptSelf_base 的运行时间为 194010.75 ms；内存使用量为 2348.00 KB 执行结果 = 50000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2) 改进版一【字典改进乘积计算】

尴尬的双层循环 尴尬通过，超过5%

import CheckFuncPerf as cfp

def productExceptSelf_ext1(nums):
 dic_nums = {}
 for iIdx in range(len(nums)):
     dic_nums[nums[iIdx]] = dic_nums.get(nums[iIdx], 0) + 1
 result = []
 for iIdx in range(len(nums)):
     imulti = 1
     for aKey in dic_nums.keys():
         if aKey != nums[iIdx]:
             imulti *= aKey ** dic_nums[aKey]
         else:
             imulti *= aKey ** (dic_nums[aKey]-1)
     result.append(imulti)
 return result

testcase_big = open(r'testcase/hot16_big.txt', mode='r', encoding='utf-8').read().replace('[', '').replace(']', '')
testcase_big = testcase_big.split(',')
nums = [int(x) for x in testcase_big]
result = cfp.getTimeMemoryStr(productExceptSelf_ext1, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))

# 运行结果
函数 productExceptSelf_ext1 的运行时间为 90.02 ms；内存使用量为 1944.00 KB 执行结果 = 50000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

3) 改进版二【字典改进乘积计算+预计算数字乘积】

改进版，然并卵，还是双层循环 微小改进，超过17%

import CheckFuncPerf as cfp

def productExceptSelf_ext2(nums):
 dic_nums = {}
 for iIdx in range(len(nums)):
     dic_nums[nums[iIdx]] = dic_nums.get(nums[iIdx], [0, 1, 1])
     dic_nums[nums[iIdx]][0] += 1
 for aKey in dic_nums.keys():
     dic_nums[aKey][1] = int(aKey ** (dic_nums[aKey][0]-1))
     dic_nums[aKey][2] = int(aKey ** dic_nums[aKey][1])
 result = []
 for iIdx in range(len(nums)):
     imulti = 1
     for bKey in dic_nums.keys():
         if bKey != nums[iIdx]:
             imulti *= dic_nums[bKey][2]
         else:
             imulti *= dic_nums[bKey][1]
     result.append(imulti)
 return result

testcase_big = open(r'testcase/hot16_big.txt', mode='r', encoding='utf-8').read().replace('[', '').replace(']', '')
testcase_big = testcase_big.split(',')
nums = [int(x) for x in testcase_big]
result = cfp.getTimeMemoryStr(productExceptSelf_ext2, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))

# 运行结果
函数 productExceptSelf_ext2 的运行时间为 46.00 ms；内存使用量为 924.00 KB 执行结果 = 50000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

4) 改进版三【前缀乘积+后缀乘积】

不再是双层循环，指标改进显著 指标优异，超越94%

import CheckFuncPerf as cfp

def productExceptSelf_ext3(nums):
 leftmultilist, rightmultilist = [1] * len(nums), [1] * len(nums)
 leftmulti, rightmulti = 1, 1
 for iIdx in range(len(nums)):
     leftmulti *= nums[iIdx]
     rightmulti *= nums[-iIdx-1]
     leftmultilist[iIdx] = leftmulti
     rightmultilist[-iIdx-1] = rightmulti
 result = [rightmultilist[1]]
 for iIdx in range(1, len(nums)-1):
     result.append(leftmultilist[iIdx-1]*rightmultilist[iIdx+1])
 result.append(leftmultilist[len(nums)-2])
 return result

testcase_big = open(r'testcase/hot16_big.txt', mode='r', encoding='utf-8').read().replace('[', '').replace(']', '')
testcase_big = testcase_big.split(',')
nums = [int(x) for x in testcase_big]
result = cfp.getTimeMemoryStr(productExceptSelf_ext3, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))

# 运行结果
函数 productExceptSelf_ext3 的运行时间为 22.00 ms；内存使用量为 2332.00 KB 执行结果 = 50000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

5) 改进版四【前缀乘积+后缀乘积+一次性分配内存】

直接分配结果集内存，不是一个元素一个元素的分配，实测有效 飞龙在天，超越97%

import CheckFuncPerf as cfp

def productExceptSelf_ext4(nums):
 leftmultilist, rightmultilist, result = [1] * len(nums), [1] * len(nums), [1] * len(nums)
 leftmulti, rightmulti = 1, 1
 for iIdx in range(len(nums)):
     leftmulti *= nums[iIdx]
     rightmulti *= nums[-iIdx - 1]
     leftmultilist[iIdx] = leftmulti
     rightmultilist[-iIdx - 1] = rightmulti
 result[0] = rightmultilist[1]
 for iIdx in range(1, len(nums) - 1):
     result[iIdx] = leftmultilist[iIdx - 1] * rightmultilist[iIdx + 1]
 result[-1] = leftmultilist[len(nums) - 2]
 return result

testcase_big = open(r'testcase/hot16_big.txt', mode='r', encoding='utf-8').read().replace('[', '').replace(']', '')
testcase_big = testcase_big.split(',')
nums = [int(x) for x in testcase_big]
result = cfp.getTimeMemoryStr(productExceptSelf_ext4, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))

# 运行结果
函数 productExceptSelf_ext4 的运行时间为 21.00 ms；内存使用量为 2252.00 KB 执行结果 = 50000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

6) 改进版五【改进空间复杂度】

不使用前缀乘积和后缀乘积数组，使用传入数组和结果数组直接计算，节省了内存分配环节，是本文最优的算法

网站波动，虚伪的95%

import CheckFuncPerf as cfp

def productExceptSelf_ext5(nums):
 result = [1] * len(nums)
 for iIdx in range(1, len(nums)):
     result[iIdx] = result[iIdx-1] * nums[iIdx-1]
 iright = 1
 for iIdx in range(1, len(nums)):
     iright *= nums[-iIdx]
     result[-iIdx-1] = result[-iIdx-1] * iright
 return result

testcase_big = open(r'testcase/hot16_big.txt', mode='r', encoding='utf-8').read().replace('[', '').replace(']', '')
testcase_big = testcase_big.split(',')
nums = [int(x) for x in testcase_big]
result = cfp.getTimeMemoryStr(productExceptSelf_ext5, nums)
print(result['msg'], '执行结果 = {}'.format(len(result['result'])))

# 运行结果
函数 productExceptSelf_ext5 的运行时间为 18.01 ms；内存使用量为 1856.00 KB 执行结果 = 50000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

4. 最优算法

根据本地日志分析，最优算法为第6种productExceptSelf_ext5

testcase_big = open(r'testcase/hot16_big.txt', mode='r', encoding='utf-8').read().replace('[', '').replace(']', '')
testcase_big = testcase_big.split(',')
nums = [int(x) for x in testcase_big]

# 6种算法本地速度实测比较    ⇒   最优算法为第6种
函数 productExceptSelf_base 的运行时间为 194010.75 ms；内存使用量为 2348.00 KB 执行结果 = 50000
函数 productExceptSelf_ext1 的运行时间为 90.02 ms；内存使用量为 1944.00 KB 执行结果 = 50000
函数 productExceptSelf_ext2 的运行时间为 46.00 ms；内存使用量为 924.00 KB 执行结果 = 50000
函数 productExceptSelf_ext3 的运行时间为 22.00 ms；内存使用量为 2332.00 KB 执行结果 = 50000
函数 productExceptSelf_ext4 的运行时间为 21.00 ms；内存使用量为 2252.00 KB 执行结果 = 50000
函数 productExceptSelf_ext5 的运行时间为 18.01 ms；内存使用量为 1856.00 KB 执行结果 = 50000
1
2
3
4
5
6
7
8
9
10
11

一日练，一日功，一日不练十日空

may the odds be ever in your favor ~