題目
給定一個(gè)整數(shù)列表 nums 涎拉，且 nums 中至少含有3個(gè)整數(shù)，請(qǐng)?jiān)诹斜碇姓页鲇扇齻€(gè)數(shù)組成的最大乘積的圆，并輸出這個(gè)乘積鼓拧。
例如：
給定一個(gè)列表：[1, 2, 3]，返回結(jié)果：6
給定一個(gè)列表：[1, 2, -3, -3, 0]越妈，返回結(jié)果：18
實(shí)現(xiàn)思路1
- 使用
排序的方式來(lái)實(shí)現(xiàn)季俩，但時(shí)間復(fù)雜度為 O(nlog(n)) - 先對(duì) nums 進(jìn)行排序，排序后就可獲取到 nums 中最小的數(shù) min1梅掠、第二小的數(shù) min2酌住、最大的數(shù) max1、第二大的數(shù) max2阎抒、第三大的數(shù) max3
- 最大乘積只會(huì)有2種組合情況：max1 * max2 * max3酪我、max1 * min1 * min2（因?yàn)?min1、min2均為負(fù)數(shù)時(shí)挠蛉，相乘可變?yōu)檎龜?shù)）祭示，從而可以得到最大乘積。
代碼實(shí)現(xiàn)1
def maximumProduct(nums):
nums.sort()
return max(nums[0] * nums[1] * nums[-1], nums[-3] * nums[-2] * nums[-1])
實(shí)現(xiàn)思路2
- 不使用排序谴古，直接遍歷一次列表即可质涛，時(shí)間復(fù)雜度O(n)
- 定義 min1、min2 為一個(gè)無(wú)窮大的數(shù)掰担，所有數(shù)都比它們谢懵健；定義 max1带饱、max2毡代、max3 為一個(gè)無(wú)窮小的數(shù)阅羹，所有數(shù)都比它們大
- 遍歷過(guò)程中，如果當(dāng)前整數(shù)小于 min1 教寂，那么將 min1 置為當(dāng)前整數(shù)捏鱼，同時(shí)需將 min2 置為原來(lái)的 min1 ；如果當(dāng)前整數(shù)大于等于 min1 且小于 min2 酪耕， 那么將 min2 置為當(dāng)前整數(shù)即可
- 遍歷過(guò)程中导梆，如果當(dāng)前整數(shù)大于 max1，那么將 max1 置為當(dāng)前整數(shù)迂烁，同時(shí)需將 max2看尼、max3 置為原來(lái)的 min1、max2盟步；如果當(dāng)前整數(shù)小于等于 max1 且大于 max2藏斩，那么將 max2 置為當(dāng)前整數(shù)，同時(shí)需將 max3 置為原來(lái)的 max2却盘；如果當(dāng)前整數(shù)小于等于 max2 且大于 max3狰域，那么將 max3 置為當(dāng)前整數(shù)即可
代碼實(shí)現(xiàn)2
def maximumProduct(nums):
min1, min2 = float("inf"), float("inf") # 定義一個(gè)無(wú)窮大的數(shù)，所有數(shù)都比 inf 小
max1, max2, max3 = float("-inf"), float("-inf"), float("-inf") # 定義一個(gè)無(wú)窮小的數(shù)谷炸，所有數(shù)都比 -inf 大
for num in nums:
if num < min1:
min1, min2 = num, min1
elif num < min2:
min2 = num
if num > max1:
max1, max2, max3 = num, max1, max2
elif num > max2:
max2, max3 = num, max2
elif num > max3:
max3 = num
num_product1 = max1 * max2 * max3
num_product2 = max1 * min1 * min2
return num_product1 if num_product1 > num_product2 else num_product2
更多Python編程題北专，等你來(lái)挑戰(zhàn)：Python編程題匯總（持續(xù)更新中……）
