【Leetcode_easy】628. Maximum Product of Three Numbers
2024-09-01 13:06:06
problem
628. Maximum Product of Three Numbers
题意：三个数乘积的最大值；
solution1:
如果全是负数，三个负数相乘还是负数，为了让负数最大，那么其绝对值就该最小，而负数排序后绝对值小的都在末尾，所以是末尾三个数字相乘，这个跟全是正数的情况一样。那么重点在于前半段是负数，后半段是正数，那么最好的情况肯定是两个最小的负数相乘得到一个正数，然后跟一个最大的正数相乘，这样得到的肯定是最大的数，所以我们让前两个数相乘，再和数组的最后一个数字相乘，就可以得到这种情况下的最大的乘积.
class Solution {
public:
int maximumProduct(vector<int>& nums) {
//positive-negtive;
sort(nums.begin(), nums.end());
int n = nums.size();
int tmp = nums[n-]*nums[n-]*nums[n-];
return max(tmp, nums[]*nums[]*nums[n-]);
}
};
solution2:找出三个最大的或者一个最大的两个最小的，比较他们的乘积，而且是O(n)的时间复杂度
注意，求解数值时候的逻辑顺序。
class Solution {
public:
int maximumProduct(vector<int>& nums) {
//positive-negtive;
int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
int min1 = INT_MAX, min2 = INT_MAX;
for (auto num : nums)
{
if(num>max1)
{
max3 = max2; max2 = max1; max1 = num;
}
else if(num>max2)
{
max3 = max2; max2 = num;
}
else if(num>max3) max3 = num;
if(num<min1)
{
min2 = min1; min1 = num;
}
else if(num<min2) min2 = num;
}
return max(max1*max2*max3, max1*min1*min2);
}
};
参考
1. Leetcode_easy_628. Maximum Product of Three Numbers;
2. Grandyang;
完
最新文章
- Mybatis XML 映射配置文件 -- 熟悉配置
- 一些MEL命令
- dump buffer cache
- Boost.Foreach
- Gradle sync failed: Gradle version 2.2 is required. Current version is 2.10.
- 使用接口的方式调用远程服务 ------ 利用动态调用服务，实现.net下类似Dubbo的玩法。
- poj 1149经典网络流构图
- Android短信备份及插入笔记
- String.split()与StringUtils.split()
- 神州数码广域网Frame-Relay封装配置（即帧中继）
- 基于Redisson实现分布式锁
- LAXCUS大数据操作系统节点挂掉后的处理
- Selector 实现原理
- 浅谈musql中using的使用---高性能(三)
- CF1119 Global Round 2
- 创建maven或者Gradle项目的时候GroupId和ArtifactId以及Version是什么意思？
- Problem 2278 YYS （FZU + java大数）
- 【转帖】Dubbo：来自于阿里巴巴的分布式服务框架
- sort函数
- c# OrderBy 实现List升序降序