前言:剑指offer刷题系列
问题:
给你一个整型数组 nums
,在数组中找出由三个数组成的最大乘积,并输出这个乘积。
示例:
输入:nums = [1,2,3]
输出:6
思路1:
-
先去计算输入列表
nums
的长度,并将结果存储在变量nlen
中。这是为了后面的条件判断做准备。 -
然后通过比较列表的长度
nlen
是否等于 3 来检查列表中是否有且仅有三个元素。如果是的话,就直接返回这三个元素的乘积,因为在只有三个元素的情况下,无需排序,直接返回乘积即可。 -
如果列表长度不等于 3,那么这一行代码对列表
nums
进行排序。排序后,nums
中的元素将按升序排列,也就是从小到大排列。 -
在计算部分,先计算了两个可能的最大乘积,然后返回其中较大的那个。
- 计算的是排序后的列表中,最小的两个数与最大的一个数的乘积。
- 计算的是排序后的列表中,最大的三个数的乘积。
这两个乘积中的较大者就是整个列表中三个数的最大乘积。
基于上述思考,代码如下:
class Solution:
def maximumProduct(self, nums: List[int]) -> int:
nlen = len(nums)
if nlen == 3:
return nums[0] * nums[1] * nums[2]
nums.sort()
return max(nums[0]*nums[1]*nums[-1],nums[-1]*nums[-2]*nums[-3])
执行结果如下图:
思路2:
- 一开始先对输入列表
nums
进行排序。排序后,nums
中的元素将按升序排列,也就是从小到大排列。 - 然后计算了排序后列表中最大的三个数的乘积。由于列表已经排序,最大的三个数将位于列表的末尾,因此通过索引
-1
、-2
和-3
可以访问到它们。这三个数相乘的结果被赋值给变量res1
。 - then,计算了排序后列表中最小的两个数与最大的一个数的乘积。
nums[0]
和nums[1]
分别是列表中的最小的两个数,而nums[-1]
是最大的一个数。这三个数相乘的结果被赋值给变量res2
。 - 最后一行比较了变量
res1
和res2
的值,然后返回其中较大的那个值。这就是函数的返回值,它表示输入列表中的三个数的最大乘积。
基于上述思考,代码如下:
class Solution:
def maximumProduct(self, nums: List[int]) -> int:
nums.sort()
# 全正数 或者 全负数
res1 = nums[-1]*nums[-2]*nums[-3]
# 有正数有负数
res2 = nums[0]*nums[1]*nums[-1]
return max(res1, res2)