专栏首页chenjx85的技术专栏leetcode-628-Maximum Product of Three Numbers

leetcode-628-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

Note:

  1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
  2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

要完成的函数:

int maximumProduct(vector<int>& nums) 

说明:

1、这道题目给了一个vector,要求返回一个最大值,这个最大值由vector中的三个元素相乘得到。

如果vector中只有正数,那么没有疑问,最大值由最大的三个元素相乘得到。

但如果vector中有负数,那么最大值也有可能由两个最小的负数乘以最大的正数得到。

但是无论如何,要不就是三个最大的正数相乘得到,要不就是两个最小的负数乘以最大的正数得到,不可能由中间的数相乘得到。

思路很清晰,代码如下:

    int maximumProduct(vector<int>& nums) 
    {
        sort(nums.begin(),nums.end());
        int a=nums[0]*nums[1]*nums[nums.size()-1];//俩最小负数乘以最大正数
        int b=nums[nums.size()-1]*nums[nums.size()-2]*nums[nums.size()-3];//三个最大的正数
        return a>b?a:b;
    }

上述代码实测69ms,beats 44.94% of cpp submissions。

2、改进:

其实我们不需要全排整个vector,我们只要部分排序之后的第一位、第二位、倒数第一位、倒数第二位以及倒数第三位的值。

所以使用nth_element来处理。代码如下:

    int maximumProduct(vector<int>& nums) 
    {
        int s1=nums.size();
        nth_element(nums.begin(),nums.begin(),nums.end());
        int a=nums[0];
        nth_element(nums.begin(),nums.begin()+1,nums.end());
        int b=nums[1];
        nth_element(nums.begin(),nums.end()-1,nums.end());
        int c=nums[s1-1];
        nth_element(nums.begin(),nums.end()-2,nums.end());
        int d=nums[s1-2];
        nth_element(nums.begin(),nums.end()-3,nums.end());
        int e=nums[s1-3];

        int f=c*d*e;
        int g=a*b*c;
        return f>g?f:g;
    }

上述代码实测56ms,beats 74.16% of cpp submissions。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • leetcode-747-Largest Number At Least Twice of Others(求vector的最大值和次大值)

    chenjx85
  • leetcode-55-跳跃游戏

    1、给定一个vector,里面存放着非负的int型整数,每一个整数代表在这个位置上可以跳跃的步数,要求判断最终能不能跳跃到vector的最后一位。

    chenjx85
  • leetcode-674-Longest Continuous Increasing Subsequence

    chenjx85
  • LintCode 恢复旋转排序数组题目分析代码

    说明 什么是旋转数组? 比如,原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,...

    desperate633
  • LeetCode-31 下一个排列

    今天我们学习第31题下一个排列,这是一个中等的数组题。我们先看看这道题的题目描述。

    用户3470542
  • 【leetcode刷题】20T39-颜色分类

    https://leetcode-cn.com/problems/sort-color

    木又AI帮
  • leetcode之移动零

    这里遍历数组,维护一个下标,当值不为0时则进行移动同时递增下标,遍历完一次之后,在从该下标起往后遍历,赋值为0。

    codecraft
  • 旋转排序的数组

    ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

    羽翰尘
  • LeetCode 448. 找到所有数组中消失的数字

    给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

    Michael阿明
  • 移动零

    一份执着✘

扫码关注云+社区

领取腾讯云代金券