跟我一起刷leetCode算法题11之 Maximum Product of Three Numbers

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

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容