628. Maximum Product of Three Numbers
这是leetCode第628题
题目
Given an integer array, find three numbers whose product is maximum and output the maximum product.
意思是说：
给出一个整数数组，找出三个数字，它们的乘积是最大的。输出最大的乘积。
数组中的整数可能为负数。
我的思路
三个整数相乘，其中必有两个数相乘是非负数。
所以，将数组排序后，两个数相乘的最大非负数就在数组的两端(绝对值最大的数，在数组两端)。
如下面这个数组：
[-99,-8,1,2,100,110] 两个数相乘的最大非负数为100*110
[-99,-188,1,2,100,110] 两个数相乘的最大非负数为-99*-188
[1,2,3,9,11] 两个数相乘的最大非负数为9*11
[-9,2,3,8,12] 两个数相乘的最大非负数为8*12
既然我们已经确定了两个数最大的乘积，那么只要我们确定第三个数，就把结果确定下来了。
假设：
把排序后的数组称为newArray，数组长度L
如果newArray[0] * newArray[1]是最大的非负整数，那么数组中剩下的最大数字，就在数组的最右边。
可以从以下例子得出上述结论：
[-9,-8,1,2,3] -9*-8*3最大
[-9,-8,-7,-7,-6,0] -9*-8*0 最大
[-9,-8,-7,-7,-6] -9*-8*-6 最大
如果newArray[L-1] * newArray[L-2]是最大的非负整数，那么数组中剩下的最大数字，就在数组的L-3位置。
可以从以下例子得出上述结论：
[1,2,3,4,6,7] 7*6*4 最大
[-1,-2,3,4,6,7] 7*6*4最大
[-5,-4,-3,-1,6,7] 7*6*-1最大
代码如下
/**
* @param {number[]} nums
* @return {number}
*/
var maximumProduct = function (nums) {
var l = nums.length;
nums.sort(function (a, b) {
return a - b;
});
max1 = nums[0] * nums[1] * nums[l - 1];
max2 = nums[l - 1] * nums[l - 2] * nums[l - 3];
return Math.max(max1, max2);
}
这是我的算法，但是我利用了sort()方法,算法的时间复杂度为O(nlogn)。
下面介绍一下时间复杂度为O(n)的算法。
/**
* @param {number[]} nums
* @return {number}
*/
var maximumProduct = function (nums) {
var min1=min2=Number.MAX_SAFE_INTEGER,
max1=max2=max3=Number.MIN_SAFE_INTEGER;
var l = nums.length;
var n = '';
for (var i = 0; i < l; i++) {
n = nums[i];
if (n <= min1) {
min2 = min1;
min1 = n;
} else if (n <= min2) {
min2 = n;
}
if (n >= max1) {
max3 = max2;
max2 = max1;
max1 = n;
} else if (n >= max2) {
max3 = max2;
max2 = n;
} else if (n >= max3) {
max3 = n;
}
}
return Math.max(min1 * min2 * max1, max1 * max2 * max3);
}
这个算法的目的，就是找出数组中的两个最小的整数，和三个最大的整数。其实就是排序后的数组中，最左侧的两个数和最右侧的三个数。
下面比较下，两种算法的效率如何？
利用下面代码生成一个长度为10000000的数组。
node product.js
product.js 的代码如下：
var fs = require("fs");
var nums =[];
var boundary = 10000000;
for(var i=0;i<boundary;i++){
var num = Math.round(Math.random()*boundary);
num = num%2===0?num:-num;
nums.push(num);
}
//转成字符串
var str = "var array=["+nums+"];module.exports=array;";
//写入Array.js文件，生成了js代码
fs.writeFile('Array.js', str, function(err) {
if (err) {
return console.error(err);
}
console.log("数据写入成功！");
});
运行我的算法：
var start = new Date().getTime();
console.log("result:"+maximumProduct(nums));
var end = new Date().getTime();
console.log("time:"+(end-start));
结果如下：
result：999999800000010000000
time:4477
运行第二种算法的结果如下：
result:999999800000010000000
time:91
很显然，第二种算法的速度更快。
