0628. Maximum Product of Three Numbers

628. Maximum Product of Three Numbers #

题目 #

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3]
Output: 6

Example 2:

Input: [1,2,3,4]
Output: 24

Note:

  1. The length of the given array will be in range [3,10^4] and all elements are in the range [-1000, 1000].
  2. Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

题目大意 #

给定一个整型数组,在数组中找出由三个数组成的最大乘积,并输出这个乘积。

解题思路 #

  • 给出一个数组,要求求出这个数组中任意挑 3 个数能组成的乘积最大的值。
  • 题目的 test case 数据量比较大,如果用排序的话,时间复杂度高,可以直接考虑模拟,挑出 3 个数组成乘积最大值,必然是一个正数和二个负数,或者三个正数。那么选出最大的三个数和最小的二个数,对比一下就可以求出最大值了。时间复杂度 O(n)

代码 #


package leetcode

import (
	"math"
	"sort"
)

// 解法一 排序,时间复杂度 O(n log n)
func maximumProduct(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	res := 1
	if len(nums) <= 3 {
		for i := 0; i < len(nums); i++ {
			res = res * nums[i]
		}
		return res
	}
	sort.Ints(nums)
	if nums[len(nums)-1] <= 0 {
		return 0
	}
	return max(nums[0]*nums[1]*nums[len(nums)-1], nums[len(nums)-1]*nums[len(nums)-2]*nums[len(nums)-3])
}

func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

// 解法二 模拟,时间复杂度 O(n)
func maximumProduct1(nums []int) int {
	max := make([]int, 0)
	max = append(max, math.MinInt64, math.MinInt64, math.MinInt64)
	min := make([]int, 0)
	min = append(min, math.MaxInt64, math.MaxInt64)
	for _, num := range nums {
		if num > max[0] {
			max[0], max[1], max[2] = num, max[0], max[1]
		} else if num > max[1] {
			max[1], max[2] = num, max[1]
		} else if num > max[2] {
			max[2] = num
		}
		if num < min[0] {
			min[0], min[1] = num, min[0]
		} else if num < min[1] {
			min[1] = num
		}
	}
	maxProduct1, maxProduct2 := min[0]*min[1]*max[0], max[0]*max[1]*max[2]
	if maxProduct1 > maxProduct2 {
		return maxProduct1
	}
	return maxProduct2
}


⬅️上一页

下一页➡️

Calendar Oct 9, 2021
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者