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 (
	"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])
}

// 解法二 模拟,时间复杂度 O(n)
func maximumProduct1(nums []int) int {
	n1, n2, n3 := -1<<63, -1<<63, -1<<63
	n4, n5 := 0, 0
	for _, v := range nums {
		if v > n1 {
			n3 = n2
			n2 = n1
			n1 = v
		} else if v > n2 {
			n3 = n2
			n2 = v
		} else if v > n3 {
			n3 = v
		}
		if v < n4 {
			n5 = n4
			n4 = v
		} else if v < n5 {
			n5 = v
		}
	}
	if n2*n3 > n4*n5 {
		return n1 * n2 * n3
	}
	return n1 * n4 * n5
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者