儿童故事网站建设,建设局网站查询,开发公司员工购房集资,网站建设和维护岗位的职责Python算法题集_除自身以外数组的乘积 题239#xff1a;除自身以外数组的乘积1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【暴力求解】2) 改进版一【字典改进乘积计算】3) 改进版二【字典改进乘积计算预计算数字乘积】4) 改进版三【前缀乘积… Python算法题集_除自身以外数组的乘积 题239除自身以外数组的乘积1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【暴力求解】2) 改进版一【字典改进乘积计算】3) 改进版二【字典改进乘积计算预计算数字乘积】4) 改进版三【前缀乘积后缀乘积】5) 改进版四【前缀乘积后缀乘积一次性分配内存】6) 改进版五【改进空间复杂度】 4. 最优算法 本文为Python算法题集之一的代码示例
题239除自身以外数组的乘积
1. 示例说明 给你一个整数数组 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) 的额外空间复杂度内完成这个题目吗 出于对空间复杂度分析的目的输出数组 不被视为 额外空间。 2. 题目解析
- 题意分解
本题为求所有子数组的乘积本题的主要计算有2处1是子数组遍历2是子数组求乘积基本的办法是双层循环挨个计算所以基本的时间算法复杂度为O(n2
- 优化思路 减少循环层次 增加分支减少计算集 采用内置算法来提升计算速度 分析题目特点分析最优解 1采用字典存储数组中每个数字的数量可以加快子数组求乘积的速度 2将字典中每个数字的乘积、少乘一次的乘积先计算出来改计算为字典查询可以加快子数组求乘积的速度 3采用类似前缀和的思路计算前缀乘积、后缀乘积这样第i个元素的除自身外数组的乘积前缀乘积i-1 * 后缀乘积i1可以减少循环层次 4进阶算法要求少用临时空间使用结果数组和原始数组可以配合完成结果计算 - 测量工具
本地化测试说明LeetCode网站测试运行时数据波动很大因此需要本地化测试解决这个问题CheckFuncPerf函数用时和内存占用测试模块已上传到CSDN地址在这里Python算法题集_检测函数用时和内存占用的模块测试的超时测试用例文件是官网的已上传到CSDN地址在这里力扣算法题除自身以外数组的乘积测试超时数组长度5W 3. 代码展开
1) 标准求解【暴力求解】
双层循环超时未过
import CheckFuncPerf as cfpdef productExceptSelf_base(nums):result []for iIdx in range(len(nums)):imulti 1for jIdx in range(len(nums)):if jIdx! iIdx:imulti * nums[jIdx]result.append(imulti)return resulttestcase_big open(rtestcase/hot16_big.txt, moder, encodingutf-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 执行结果 500002) 改进版一【字典改进乘积计算】
尴尬的双层循环 尴尬通过超过5%
import CheckFuncPerf as cfpdef productExceptSelf_ext1(nums):dic_nums {}for iIdx in range(len(nums)):dic_nums[nums[iIdx]] dic_nums.get(nums[iIdx], 0) 1result []for iIdx in range(len(nums)):imulti 1for 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 resulttestcase_big open(rtestcase/hot16_big.txt, moder, encodingutf-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 执行结果 500003) 改进版二【字典改进乘积计算预计算数字乘积】
改进版然并卵还是双层循环 微小改进超过17%
import CheckFuncPerf as cfpdef 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] 1for 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 1for bKey in dic_nums.keys():if bKey ! nums[iIdx]:imulti * dic_nums[bKey][2]else:imulti * dic_nums[bKey][1]result.append(imulti)return resulttestcase_big open(rtestcase/hot16_big.txt, moder, encodingutf-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 执行结果 500004) 改进版三【前缀乘积后缀乘积】
不再是双层循环指标改进显著 指标优异超越94%
import CheckFuncPerf as cfpdef productExceptSelf_ext3(nums):leftmultilist, rightmultilist [1] * len(nums), [1] * len(nums)leftmulti, rightmulti 1, 1for iIdx in range(len(nums)):leftmulti * nums[iIdx]rightmulti * nums[-iIdx-1]leftmultilist[iIdx] leftmultirightmultilist[-iIdx-1] rightmultiresult [rightmultilist[1]]for iIdx in range(1, len(nums)-1):result.append(leftmultilist[iIdx-1]*rightmultilist[iIdx1])result.append(leftmultilist[len(nums)-2])return resulttestcase_big open(rtestcase/hot16_big.txt, moder, encodingutf-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 执行结果 500005) 改进版四【前缀乘积后缀乘积一次性分配内存】
直接分配结果集内存不是一个元素一个元素的分配实测有效 飞龙在天超越97%
import CheckFuncPerf as cfpdef productExceptSelf_ext4(nums):leftmultilist, rightmultilist, result [1] * len(nums), [1] * len(nums), [1] * len(nums)leftmulti, rightmulti 1, 1for iIdx in range(len(nums)):leftmulti * nums[iIdx]rightmulti * nums[-iIdx - 1]leftmultilist[iIdx] leftmultirightmultilist[-iIdx - 1] rightmultiresult[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 resulttestcase_big open(rtestcase/hot16_big.txt, moder, encodingutf-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 执行结果 500006) 改进版五【改进空间复杂度】
不使用前缀乘积和后缀乘积数组使用传入数组和结果数组直接计算节省了内存分配环节是本文最优的算法
网站波动虚伪的95%
import CheckFuncPerf as cfpdef productExceptSelf_ext5(nums):result [1] * len(nums)for iIdx in range(1, len(nums)):result[iIdx] result[iIdx-1] * nums[iIdx-1]iright 1for iIdx in range(1, len(nums)):iright * nums[-iIdx]result[-iIdx-1] result[-iIdx-1] * irightreturn resulttestcase_big open(rtestcase/hot16_big.txt, moder, encodingutf-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 执行结果 500004. 最优算法
根据本地日志分析最优算法为第6种productExceptSelf_ext5
testcase_big open(rtestcase/hot16_big.txt, moder, encodingutf-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一日练一日功一日不练十日空
may the odds be ever in your favor ~
