专栏首页Michael阿明学习之路LeetCode 628. 三个数的最大乘积

LeetCode 628. 三个数的最大乘积

1. 题目

给定一个整型数组,在数组中找出由三个数组成的最大乘积,并输出这个乘积。

示例 1:
输入: [1,2,3]
输出: 6

示例 2:
输入: [1,2,3,4]
输出: 24

注意:
给定的整型数组长度范围是[3,10^4],数组中所有的元素范围是[-1000, 1000]。
输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-product-of-three-numbers 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

3数的最大乘积只能是 max(最大的3个,最小的2个*最大的1个)

2.1 排序

O(n*lgn)时间复杂度

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

2.2 线性扫描

O(n)时间复杂度

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int m1,m2,m3,n1,n2;
        m1=m2=m3=INT_MIN;
        n1=n2=INT_MAX;
        for(int &x : nums)
        {
        	if(x >= m1)
        	{
        		m3 = m2;
        		m2 = m1;
        		m1 = x;
        	}
        	else if(x >= m2)
        	{
        		m3 = m2;
        		m2 = x;
        	}
        	else if(x > m3)
        		m3 = x;

        	if(x <= n1)
        	{
        		n2 = n1;
        		n1 = x;
        	}
        	else if(x < n2)
        		n2 = x;
        }
        return max(m1*m2*m3, m1*n1*n2);
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 261. 以图判树(全部连通+边数=V-1)

    给定从 0 到 n-1 标号的 n 个结点,和一个无向边列表(每条边以结点对来表示), 请编写一个函数用来判断这些边是否能够形成一个合法有效的树结构。

    Michael阿明
  • LeetCode 324. 摆动排序 II

    给定一个无序的数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。

    Michael阿明
  • 程序员面试金典 - 面试题 17.19. 消失的两个数字(数学/位运算)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/missing-two-lcci 著作权归领扣网络所...

    Michael阿明
  • 浅谈什么是分治算法

      分治算法,根据字面意思解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接...

    五分钟学算法
  • 冒泡排序图解+代码示例

  • 选择排序图解与代码示例

  • 图的构建

    每天学Java
  • leetcode-169-Majority Element

    chenjx85
  • LeetCode 1346. Check If N and Its Double Exist

    ShenduCC
  • LeetCode 每日一题169: 求众数

    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

    benny

扫码关注云+社区

领取腾讯云代金券