本文主要是介绍leetcode题:628. 三个数的最大乘积(简单),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、题目描述:628. 三个数的最大乘积(简单)
给定一个整型数组,在数组中找出由三个数组成的最大乘积,并输出这个乘积。
示例 1:
输入: [1,2,3]
输出: 6
示例 2:输入: [1,2,3,4]
输出: 24
注意:给定的整型数组长度范围是[3,104],数组中所有的元素范围是[-1000, 1000]。
输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-product-of-three-numbers
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、解题思路
1、找到数组的最大3个正整数,最小的2个负数,最小的2个正数,最大的3个负数,一个标记是否存在0。
2、当正数数量大于3或者正数个数大于1,负数有2个以上。则最大乘积一定是正的。所以此时判断3个正数乘积,最大正数以及最小的两个负数的乘积的大小,取较大值。
3、如果上述条件不满足并且存在0元素,则最大乘积为0
4、如果上述条件不满足,并且有3个负数以上,则最大乘积为3个最小负数的值。
5、如果上述条件不满足,如果负数只有两个,并且正数只有一个,则最大乘积为两个最小负数和最小正数的乘积。
三、代码
class Solution {
public:int maximumProduct(vector<int>& nums) {vector<int> zheng;vector<int> fu;vector<int> zheng_min;vector<int> fu_min;bool is_zero =false;for(int i = 0;i<nums.size(); i++){if(nums[i] > 0){addzheng(zheng,nums[i]);addzheng_min(zheng_min,nums[i]);}if(nums[i] < 0){addfu(fu,nums[i]);addfu_min(fu_min,nums[i]);}if(nums[i] == 0){is_zero = true;}}int max_all = INT_MIN;int max_count = 1;print(zheng);print(fu);print(zheng_min);print(fu_min);cout<<"is_zero="<<is_zero<<endl;if(zheng.size() == 3){int max_zheng = 1;for(int i = 0; i< zheng.size();i++){max_count *= zheng[i];if(zheng[i] > max_zheng){max_zheng = zheng[i];}}max_all = max_count;int max_fu = max_zheng;for(int i = 0 ;i < fu.size();i++){max_fu *= fu[i];}max_count = max(max_count,max_fu);}else if(zheng.size() == 1 && fu.size() >= 2){max_count = zheng[0] * fu[0] * fu[1];}else if(is_zero == true){max_count = 0;}else if(zheng_min.size() == 2 && fu_min.size() == 1){max_count = zheng_min[0] * zheng_min[1]*fu_min[0];}else if(fu_min.size() == 3 && zheng.size() == 0){max_count = fu_min[0] * fu_min[1] * fu_min[2];}return max_count;}void addzheng(vector<int> & dp,int num){if(dp.size() < 3)dp.push_back(num);else{int min_index = 0;for(int i = 1;i<dp.size();i++){if(dp[i] < dp[min_index]){min_index = i;}}if(dp[min_index] < num)dp[min_index] = num;}}void addfu(vector<int> & dp,int num){if(dp.size() < 2)dp.push_back(num);else{int min_index = 0;for(int i = 1;i<dp.size();i++){if(dp[i] > dp[min_index]){min_index = i;}}if(dp[min_index] > num)dp[min_index] = num;}}void addfu_min(vector<int> & dp,int num){if(dp.size() < 3)dp.push_back(num);else{int min_index = 0;for(int i = 1;i<dp.size();i++){if(dp[i] < dp[min_index]){min_index = i;}}if(dp[min_index] < num)dp[min_index] = num;}}void addzheng_min(vector<int> & dp,int num){if(dp.size() < 3)dp.push_back(num);else{int min_index = 0;for(int i = 1;i<dp.size();i++){if(dp[i] > dp[min_index]){min_index = i;}}if(dp[min_index] > num)dp[min_index] = num;}}void print(vector<int>& dp){for(int i = 0;i<dp.size();i++){cout<<dp[i]<<",";}cout<<endl;}
};
这篇关于leetcode题:628. 三个数的最大乘积(简单)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!