国家公务员考试网,联欢晚会,过年好-奥利奥实验室,甜品的天堂,在线实验

admin 2019-05-16 阅读:270

技能进步是一个按部就班的进程,所以我讲的leetcode算法题从最简略的level开端写的,然后> 到中级难度,最后到hard难度悉数完。现在我挑选C言语,Python和Java作为完成言语,因为这三种言语仍是比较典型的。因为篇幅和> 精力有限,其他言语的完成有爱好的朋友请自己测验。初级难度说的差不多的时分,我计划再加点其他内容,我或许会从操作系统到协议栈,从分布式> 聊到大数据结构,从大数据聊到人工智能,... ...。

假如有任何问题可以在文章后谈论或许私信给我。

继续共享,敬请您的重视。

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

问题描绘:

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

注:

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

示例:

C言语完成:

经过调查咱们很简略发现,三数最大乘积只要两种状况:

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

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

第一种状况很简略了解,尤其在nums的负数数量小于1的状况下。

当nums存在两个或许两个以上负数的时分,最小的两个负数的乘积有或许构成一个较大的正数,所以这个时分第二种状况是或许的。所以咱们需求一起考虑这两种或许。

详细解题的计划,至少有三种以上。

第一种:直接排序

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

这种办法完成简略,可是功率欠安。因为实际上,除了3个最大数和2个最小数外,对其他元素进行排序都是剩余的。假如nums的长度很大,这种耗费会比较显着。

第二种:二叉堆

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

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

详细完成,咱们别离需求一个最小堆和一个最大堆来别离寄存最小数和最大数,堆的长度别离是2和3。关于java和python来说,是比较简略完成的。可以参阅"第123篇"

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

实际上,因为标题只要求3个数的乘积,因而咱们可以直接经过一次对nums的遍历就可以找到3个最大数和2个最小数。

留意这只是是因为标题的原因,咱们才可以用这种办法,假如求最大数或最小数的个数比较多,这种办法就不太适宜了,引荐用二叉堆来完成。

咱们用第三种办法来完成。

代码如下:

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

Java言语完成:

Java 的完成与C言语完成相似,不再撰述:代码如下:

Python言语完成:

python天然也可以用上面的完成,可是我引荐用heapq来完成,简略且功率也不错。代码如下:


谢谢我们一直以来的重视和支撑!

我一直在尽力的写好每一篇文章,画好每一份插图。可是作为一个996从业人员,时刻精力非常有限。所以针对谈论部分,今后只答复粉丝的问题和私信。期望只是是路过的朋友可以谅解,期望更多人重视《吾是我师》,谢谢!