|
2022.7.14今天你刷题了吗？
题目：
给你一个整型数组?nums?，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
分析：
给定一个正负都有的整数数组，求出其中最大的三个数乘积。
思路：对于全是正数的数组，那么就取最后三个，如果数组有正负，那么最大成绩可能为，最小的两个负数和最大的正数乘积。分布如下：
-6，-5 ，1，2，3，4? ?最大为 -6*-5*4
-6，-5，4，7，8，9? ?最大为7*8*9
因此需要判断后三个之乘积和前两个和最后一个乘积比较大小。
思路：我们对数组进行排序，然后按照上面说的两个负方式进行判断。
解析：
1.排序
class Solution {
public:
int maximumProduct(vector<int>& nums) {
sort(nums.begin(),nums.end());
int n=nums.size();
return max(nums[0]*nums[1]*nums[n-1],nums[n-1]*nums[n-2]*nums[n-3]);
}
};
2.比较大小
思路如上，但是不排序了，而是找到我们说的那5个数，然后比较。
注意：这里的排序比大小是一种经典的方法。
对于三个数排大小。利用三个m1，m2，m3=int_min。然后判断当前数的三种比较情况
| num>m1 | m3=m2 m2=m1 m1=num | | num>m2 | m3=m2 m2=num | | num>m3 | m3=num |
class Solution {
public:
int maximumProduct(vector<int>& nums) {
int min_first = INT_MAX,min_second = INT_MAX;
int max_first = INT_MIN, max_second = INT_MIN, max_third = INT_MIN;
for (int num : nums)
{
if (num < min_first)
{
min_second = min_first;
min_first = num;
}
else if (min_second > num )
{
min_second = num;
}
if (num > max_first)
{
max_third = max_second;
max_second = max_first;
max_first = num;
}
else if ( num > max_second)
{
max_third = max_second;
max_second = num;
}
else if ( num > max_third)
{
max_third = num;
}
}
return max(max_first * max_second * max_third, max_first * min_first * min_second);
}
};
|