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

很显然，第二种算法的速度更快。