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 条评论
登录 后参与评论

相关文章

来自专栏HTML5学堂

算法之旅 | 快速排序法

HTML5学堂-码匠:前几期“算法之旅”跟大家分享了冒泡排序法和选择排序法,它们都属于时间复杂度为O(n^2)的“慢”排序。今天跟大家分享多种排序算法里使用较广...

3495
来自专栏云霄雨霁

排序算法总结

1240
来自专栏趣谈编程

希尔排序

1976
来自专栏人工智能头条

写算法,用 C++ 还是用 Java ,差别大吗?

今天带来的文章,是 GitChat 签约作者王晓华在不断被读者吐槽:“好好一本算法书为什么要用 C++ 来写” 时,万般无奈下憋出来的。

2112
来自专栏北京马哥教育

看完这篇,你就知道Python生成器是什么

生成器是 Python 初级开发者最难理解的概念之一,虽被认为是 Python 编程中的高级技能,但在各种项目中可以随处见到生成器的身影,你得不得去理解它、使用...

37612
来自专栏PPV课数据科学社区

【学习】视觉直观感受 7 种常用排序算法

10月14日发布《统计世界的十大算法》后,很多朋友在后台询问,哪里有“视觉直观感受 7 种常用排序算法”,今天分享给大家,感谢todayx.org。 1. 快速...

3215
来自专栏PHP在线

PHP 排序算法实现讲解

所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序 算法在很多领域得到相...

2905
来自专栏机器学习算法与Python学习

动画+原理+代码,解读十大经典排序算法

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

1223
来自专栏用户画像

排序算法 归纳总结

一、直接插入排序、冒泡排序和简单选择排序是最基本的排序方法,它们主要用于元素个数n(n<10000)不是很大的情形。

822
来自专栏人工智能LeadAI

排序算法对比、总结(Python代码)

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

3988

扫码关注云+社区

领取腾讯云代金券