题目
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:
- The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
- Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.
解题思路
主要问题在负数的考虑，但是一共三个数，所以如果有负数的话一定是两个负数，一个正数，这样的话肯定是最小的两个负数和最大的那个正数相乘
- 如果只有三个数，直接返回三个数的乘积
- 将nums有小到大排序，如果nums中全为正数，则取最大三个数相乘
- 如果nums中有负数，则判断最小的两个数乘积nums[0] * nums[1]和倒数第二，第三大的两个数nums[len1 - 2] * nums[len1 - 3]乘积的大小，选较大的和最大的数相乘
代码
MaximumProduct.go
package _628_Maximum_Product_Three_Numbers
import (
"sort"
"fmt"
)
func MaximumProduct(nums []int) int {
len1 := len(nums)
if len1 == 3 {
return nums[0] * nums[1] * nums[2]
}
sort.Ints(nums)
fmt.Printf("int:%+v\n", nums)
if (nums[0] * nums[1]) > (nums[len1 - 2] * nums[len1 - 3]) {
return nums[0] * nums[1] * nums[len1 - 1]
} else {
return nums[len1 - 1] * nums[len1 - 2] * nums[len1 - 3]
}
}
测试
MaximumProduct_test.go
package _628_Maximum_Product_Three_Numbers
import "testing"
func TestMaximumProduct(t *testing.T) {
var tests = []struct{
input []int
output int
}{
{[]int{1,2,3}, 6},
{
[]int{-710,-107,-851,657,-14,-859,278,-182,-749,718,-640,127,-930,-462,694,969,143,309,904,-651,160,451,-159,-316,844,-60,611,-169,-73,721,-902,338,-20,-890,-819,-644,107,404,150,-219,459,-324,-385,-118,-307,993,202,-147,62,-94,-976,-329,689,870,532,-686,371,-850,-186,87,878,989,-822,-350,-948,-412,161,-88,-509,836,-207,-60,771,516,-287,-366,-512,509,904,-459,683,-563,-766,-837,-333,93,893,303,908,532,-206,990,280,826,-13,115,-732,525,-939,-787},
972256230,
},
}
for _, v := range tests {
ret := MaximumProduct(v.input)
if ret == v.output {
t.Logf("pass")
} else {
t.Errorf("fail, want %+v, get %+v", v.output, ret)
}
}
}
