j
jaryue
V1
2023/04/23阅读:11主题:默认主题
leetcode 628. 三个数的最大乘积
leetcode 628. 三个数的最大乘积
题目描述
-
三个数的最大乘积
给你一个整型数组 nums ,在数组中找出由三个数组成的最大乘积,并输出这个乘积。
示例 1:
输入:nums = [1,2,3] 输出:6 示例 2:
输入:nums = [1,2,3,4] 输出:24 示例 3:
输入:nums = [-1,-2,-3] 输出:-6
提示:
3 <= nums.length <= 104 -1000 <= nums[i] <= 1000
解题思路
法1
排序+模拟\
-
对数组进行排序 -
找出乘积最大的三个数
-
a[0]*a[1]*a[len-1] -
a[len-1]*a[len-2]*a[len-3]
这两种情况下可以取到最大值
-
时间复杂度(O(nlogn)) -
空间复杂度(O(1))
执行结果
法1
func maximumProduct(nums []int) int {
l := len(nums)
if l <= 3 {
return nums[1] * nums[2] * nums[0]
}
sort.Ints(nums)
if nums[0] > 0 && nums[l-1] < 0 || nums[0]*nums[1]*nums[l-1] < nums[l-1]*nums[l-2]*nums[l-3] {
return nums[l-1] * nums[l-2] * nums[l-3]
}
return nums[0] * nums[1] * nums[l-1]
}
执行结果: 通过 显示详情 查看示例代码 添加备注
执行用时: 48 ms , 在所有 Go 提交中击败了 66.67% 的用户 内存消耗: 6.3 MB , 在所有 Go 提交中击败了 72.73% 的用户 通过测试用例: 92 / 92 炫耀一下:
优化结构
func maximumProduct(nums []int) int {
l := len(nums)
sort.Ints(nums)
if nums[0]*nums[1]*nums[l-1] < nums[l-1]*nums[l-2]*nums[l-3] {
return nums[l-1] * nums[l-2] * nums[l-3]
}
return nums[0] * nums[1] * nums[l-1]
}
执行结果: 通过 显示详情 查看示例代码 添加备注
执行用时: 44 ms , 在所有 Go 提交中击败了 73.33% 的用户 内存消耗: 6.3 MB , 在所有 Go 提交中击败了 72.73% 的用户 通过测试用例: 92 / 92 炫耀一下:
作者介绍
j
jaryue
V1