j

jaryue

V1

2023/04/23阅读:11主题:默认主题

leetcode 628. 三个数的最大乘积

leetcode 628. 三个数的最大乘积


题目描述

  1. 三个数的最大乘积

给你一个整型数组 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

排序+模拟\

  1. 对数组进行排序
  2. 找出乘积最大的三个数
  • 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