LeetCode628. Maximum Product of Three Numbers 解题
LeetCode628. 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
注意事项：
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.
- 数组的长度不会超过104也不会少于3，其中元素的值在[-1000,1000]范围内
- 他们的积不会超过32位整型数可以表示的范围，也就是说你可以用int 来保存结果
解题思路
我首先想到的方法就是先将他们排序，然后找最大的三个数相乘就是了。 但是当我想用C++自带的sort()函数的时候，我却死活导不进去algorithm包，没办法，只好自己写排序了，我就找了个快速排序的算法写。 然后我发现事情并没有那么简单，因为还存在负数，当遇到[-9,-8,-2,-1,6]这种情况的时候就不能单纯地找最大的三个了，因为负负得正，应该取最小的两个和最大的一个；同时如果我找好的三个数里头有一个为0，那就得换一个相邻的数代替。所以本以为寥寥几行可以搞定的代码最后写成了好几十行。
class Solution {
public:
int partition(vector<int> &array, int low, int high) {
int key = array[low];
while (low < high)
{
while (low < high && key <= array[high]) //如果array[high]大于键值，那么本就应该在键值右边
high--; //因此将high下标向前移动，直至找到比键值小的值，此时交换这两个值
swap(array[low], array[high]);
while (low < high && key >= array[low])
low++;
swap(array[low], array[high]);
}
return low;//返回key值的下标
}
void mySort(vector<int> &nums, int left, int right) {
int pivot;
if (left1);
mySort(nums, pivot + 1, right);
}
}
int maximumProduct(vector<int>& nums) {
int result,resultA;
int* count=new int[3];
int i;
//special case
if(nums.size()==3)
{
result=nums[0]*nums[1];
result*=nums[2];
return result;
}
//give it a sort
mySort(nums, 0, nums.size()-1);
count[2]=nums[nums.size()-1];
count[1]=nums[nums.size()-2];
count[0]=nums[nums.size()-3];
if(count[1]<0&&count[0]<0){// case -x, -x, x
count[1]=nums[1];
count[0]=nums[0];
}
for(i=0;i<3;i++){//if anyone is 0, get others
if(count[i]==0)
count[i]=nums[nums.size()-4-i];
}
//count product
result=count[0]*count[1];
result*=count[2];
//try the product of two -x
resultA=nums[0]*nums[1];
resultA*=count[2];
return result>resultA?result:resultA;
}
};更好的算法
leetcode比杭电OJ和POJ好的一个方面就是它在AC之后可以看到别人的代码，按效率排好序的，这样可以让人通过看更优秀的算法得到提高
这段代码的思路是按大小顺序维护五个变量：最大的三个(max3>max2>max1)和最小的两个(min1
class Solution {
public:
int maximumProduct(vector<int>& nums) {
if(nums.size() == 3){
return nums[0] * nums[1] * nums[2];
}
int max1 = INT_MIN;
int max2 = INT_MIN;
int max3 = INT_MIN;
int min1 = INT_MAX;
int min2 = INT_MAX;
for(int i = 0; i < nums.size(); i++){
if(nums[i] >= max1){
max3 = max2;
max2 = max1;
max1 = nums[i];
}
else if(nums[i] >= max2){
max3 = max2;
max2 = nums[i];
}
else if(nums[i] >= max3){
max3 = nums[i];
}
if(nums[i] <= min1){
min2 = min1;
min1 = nums[i];
}
else if(nums[i] <= min2){
min2 = nums[i];
}
}
return max(max1 * max2 * max3, max1 * min1 * min2);
}
};