[LeetCode] 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,104] 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.

这道题博主刚开始看的时候,心想直接排序,然后最后三个数字相乘不就完了,心想不会这么Easy吧,果然被OJ无情打脸,没有考虑到负数和0的情况。这道题给了数组的范围,至少三个,那么如果是三个的话,就无所谓了,直接相乘返回即可,但是如果超过了3个,而且有负数存在的话,情况就可能不一样,我们来考虑几种情况,如果全是负数,三个负数相乘还是负数,为了让负数最大,那么其绝对值就该最小,而负数排序后绝对值小的都在末尾,所以是末尾三个数字相乘,这个跟全是正数的情况一样。那么重点在于前半段是负数,后半段是正数,那么最好的情况肯定是两个最小的负数相乘得到一个正数,然后跟一个最大的正数相乘,这样得到的肯定是最大的数,所以我们让前两个数相乘,再和数组的最后一个数字相乘,就可以得到这种情况下的最大的乘积。实际上我们并不用分情况讨论数组的正负,只要把这两种情况的乘积都算出来,比较二者取较大值,就能涵盖所有的情况,从而得到正确的结果,参见代码如下:

class Solution {
public:
int maximumProduct(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int p = nums[] * nums[] * nums[n - ];
return max(p, nums[n - ] * nums[n - ] * nums[n - ]);
}
};

下面这种方法由网友hello_world00提供,找出3个最大的数 || 找出一个最大的和两个最小的,相乘对比也能得到结果,而且是O(n)的时间复杂度,参见代码如下:

解法二:

class Solution {
public:
int maximumProduct(vector<int>& nums) {
int mx1 = INT_MIN, mx2 = INT_MIN, mx3 = INT_MIN;
int mn1 = INT_MAX, mn2 = INT_MAX;
for (int num : nums) {
if (num > mx1) {
mx3 = mx2; mx2 = mx1; mx1 = num;
} else if (num > mx2) {
mx3 = mx2; mx2 = num;
} else if (num > mx3) {
mx3 = num;
}
if (num < mn1) {
mn2 = mn1; mn1 = num;
} else if (num < mn2) {
mn2 = num;
}
}
return max(mx1 * mx2 * mx3, mx1 * mn1 * mn2);
}
};

参考资料:

https://discuss.leetcode.com/topic/93690/java-easy-ac

 

LeetCode All in One 题目讲解汇总(持续更新中...)

上一篇:【转】Syncthing的安装与使用


下一篇:自定义admin管理工具(stark组件)