LeetCode基础算法题第124篇:求数组中三个数乘积的最大值

十字绣??????? 2019-09-20???来源:张哥谈车
LeetCode基础算法题第124篇:求数组中三个数乘积的最大值

技术提高是一个循序渐进的过程,所以我讲的leetcode算法题从最简单的level开始写的,然后> 到中级难度,最后到hard难度全部完。目前我选择C语言,Python和Java作为实现语言,因为这三种语言还是比较典型的。由于篇幅和> 精力有限,其他语言的实现有兴趣的朋友请自己尝试。初级难度说的差不多的时候,我打算再加点其他内容,我可能会从操作系统到协议栈,从分布式> 聊到大数据框架,从大数据聊到人工智能,... ...。

如果有任何问题可以在文章后评论或者私信给我。

持续分享,敬请您的关注。

LeetCode 628. 三个数的最大乘积 (Maximum Product of Three Numbers)

问题描述:

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

注:

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

示例:

LeetCode基础算法题第124篇:求数组中三个数乘积的最大值

C语言实现:

通过观察我们很容易发现,三数最大乘积只有两种情况:

1. nums的三个最大数乘积;

2. nums的最大数和两个最小数的乘积;

第一种情况很容易理解,尤其在nums的负数数量小于1的情况下。

当nums存在两个或者两个以上负数的时候,最小的两个负数的乘积有可能形成一个较大的正数,所以这个时候第二种情况是可能的。所以我们需要同时考虑这两种可能。

具体解题的方案,至少有三种以上。

第一种:直接排序

先对nums排序,得到一个有序数列。然后比较最大的3个数的乘积以及最大数和两个最小数的乘积哪一个更大,返回最大的那个。

这种方法实现简单,但是效率不佳。因为实际上,除了3个最大数和2个最小数外,对其余元素进行排序都是多余的。如果nums的长度很大,这种消耗会比较明显。

第二种:二叉堆

其实,我们并不需要一个完整的有序数列,我们只需要知道3个最大数和2个最小数。

我们上一期说道了二叉堆,这道题也很适合用二叉堆来解。

具体实现,我们分别需要一个最小堆和一个最大堆来分别存放最小数和最大数,堆的长度分别是2和3。对于java和python来说,是比较容易实现的。可以参考"第123篇"

第三种:一次遍历获取最大值和最小值

实际上,由于题目只要求3个数的乘积,因此我们可以直接通过一次对nums的遍历就可以找到3个最大数和2个最小数。

注意这仅仅是因为题目的原因,我们才可以用这种办法,如果求最大数或最小数的个数比较多,这种方法就不太合适了,推荐用二叉堆来实现。

我们用第三种方法来实现。

代码如下:

LeetCode基础算法题第124篇:求数组中三个数乘积的最大值

我们通过在遍历的过程中,不断的比较,交互元素来找到最大值很最小值。

LeetCode基础算法题第124篇:求数组中三个数乘积的最大值

Java语言实现:

Java 的实现与C语言实现类似,不再撰述:代码如下:

LeetCode基础算法题第124篇:求数组中三个数乘积的最大值

LeetCode基础算法题第124篇:求数组中三个数乘积的最大值

Python语言实现:

python自然也可以用上面的实现,但是我推荐用heapq来实现,简单且效率也不错。代码如下:

LeetCode基础算法题第124篇:求数组中三个数乘积的最大值

LeetCode基础算法题第124篇:求数组中三个数乘积的最大值


谢谢大家一直以来的关注和支持!

我一直在努力的写好每一篇文章,画好每一份插图。但是作为一个996从业人员,时间精力十分有限。所以针对评论部分,以后只回答粉丝的问题和私信。希望仅仅是路过的朋友能够体谅,希望更多人关注《吾是我师》,谢谢!