拼夕夕2018校招:最大乘积

拼夕夕2018校招:最大乘积

这道题目来自 2018年拼夕夕的校招,我从牛客网上刷到这个题。
https://www.nowcoder.com/practice/5f29c72b1ae14d92b9c3fa03a037ac5f

题目可以自行去看,我这里再简单提一下。

一. 题目

给定一个无序数组,包含正数、负数和0,要求从中找出3个数的乘积,使得乘积最大,要求时间复杂度:O(n),空间复杂度:O(1)

示例如下。
image.png

二.分析

先简单提一下:

以前刷LeetCode是直接写方法,现在用牛客这个在线编译器还不太习惯。
首先我是用java写的,牛客这里的java代码,会要求写一个Main类,然后写main方法,其次,输入是需要写从控制台读取,输出是运算结果,所以读取数据是需要自己写的。
再就是java要导包,其实记几个重要的包就可以满足了。
千万不要以为java 可以这么写:

1
important java.*;

java里面这么导包是不可以的。

正式分析:

看分析可以对照代码看,我贴的代码分为了几个部分,可以对应着看。

A: 输入
最开始是想着怎么输入,用了一个nextLine读取一行,然后又用split切片,怎么也AC不过,后来发现不能这么写,于是就去参考了大佬的输入(仅仅是输入部分……哈哈哈),发现他写的是先输入n这个值,然后再输入数据,那我就觉得这个题目出的不严谨……后来看了一道腾讯的,就很清楚让你先输入什么,再输入什么。

常刷LeetCode,对于这种不太熟悉,暂且不考虑,这不是我们的重点,我们从控制台接收这个数组,存在myData 里,这里注意要是Long型的,否则可能会有溢出之类的。

B:排序
一开始想的很复杂,情况各异,主要是局限于他所强调的On的算法复杂度,但是对于算法题的话,我觉得不太可能是让你一种一种的去想,于是干脆换了个思路。

由于它要求On的复杂度,所以我就一直没有考虑排序。
Java里面Arrays.sort()方法是一个封装好的排序方法,里面是二轴快排,对于这个排序比快速排序高级一些,但是不太了解,感兴趣的可以自行研究研究。

但是最后实在想不出好方法,然后我就用了这个方法。

C:处理
可以看我对排完序的数据进行的操作,我的思路是,排好序的数组,如果要找三个数的乘积最大,只有两种情况,
case 1.一种是数组的第0位,第1位和最后一位
case 2.第二种是数组的倒数三位

然后再从这两种情况里选到底是哪个大。
最后输出就是所求。

那为什么会这样呢?
我们举个例子。

这里是有>=2个负数的情况。
原始数据: -2 -3 -1 1 0 4 3
排序后:-3 -2 -1 0 1 3 4
所求的case 1 : -3 -2 4 = 24
所求的case 2 :1 3 4 = 12
那么最后的输出即是24

我们分析简单情况,假如说数组中只有正数和0,那么最大值乘积一定产生在排序后的数组的最后3位 【即case2】

此外,众所周知,负负得正,则肯定会有两个负数 再乘一个正数产生最大值的情况。
那最大值会在哪里产生,负负得正,我们就要找两个最小的负数,如上面一个例子,-3 和 -2 ,求出正数后,只需再找一个最大值即可,从哪里产生?当然是最后一位。 【即case1】

有童鞋看到这里可能就想着分case1和case2来判断了,但是这里其实就像我那样写即可,只需要比较一下哪个大就OK。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.io.*;
import java.util.*;

public class Main{
public static void main(String[] args) throws Exception{
long sum = 1;

//A,
//输入数据,秀儿。
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] myData = new long[n];
for (int i = 0; i < n ; i++) {
myData[i] = sc.nextLong();
}

//B,
//排序
Arrays.sort(myData);

//C,
//排序之后,从起始位置开始取值,有两种情况。
//第一种:0位 * 1位 * 最后一位
//第二种:最后一位 * 倒二 * 倒3
//最大值只产生于这两种情况中
long s1 = myData[0] * myData[1] * myData[n - 1];
long s2 = myData[n - 1] * myData[n - 2] * myData[n - 3];
sum = s1 > s2 ? s1 : s2;


//打印最终值
System.out.print(sum);

}
}

三. 运行结果

我们先看题目的时空限制。

看看我写的程序的时空
image.png

其实是在它的要求之内的,只不过对于On我还真是没别的思路了。
但是个人觉得我这个方法还是挺通俗易懂的,大致浏览了一下别人的算法,也有和我类似的实现,下面再说一个别的大佬的实现。

四. 其他实现

我们看一下湖南大学secndf大佬的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 /**
* 思路:三个数乘积最大,那么肯定包含其中最大的数,然后就只要比较最小的两个数乘积和第二第三大的两个数乘积。
* m1,m2是最小的两个数,max,h2,h1为第一/二/三大的数
*/
public static long maxTriMultiply(long A[]){
long m1 = Integer.MAX_VALUE, m2 = Integer.MAX_VALUE, h1 = Integer.MIN_VALUE, h2 = Integer.MIN_VALUE, max = Integer.MIN_VALUE;


for(int i=0;i < A.length;++i){
if(A[i]>max){
h1=h2;
h2=max;
max = A[i];
}else if(A[i]>h2){
h1=h2;
h2 = A[i];
}else if(A[i]>h1){
h1=A[i];
}
if(A[i] < m1){
m2=m1;
m1=A[i];
}else if(A[i] < m2)
m2=A[i];
}


max = max * m1 * m2 > max * h1 * h2 ? max * m1 * m2 : max * h1 * h2;
return max;
}

可以看到,他确定了两个最小的数,三个最大的数。
然后比较了我上面所提到的case1 和 case2 两种情况

与我不同的是,他为了实现On的算法,仅用了一遍遍历来找这些值。【自愧不如,以为要找到它们很麻烦,就没多想】

其实仔细看来也并不麻烦,举个例子,我们用简单选择排序的时候是怎么操作的?就是确定一个值,然后不断找比它小的值,找遍所有,确定最小值的序号,再进行交换,这里也是,只不过多了 第 n 小(大)的说法,

举个例子。
-1 4 2 0 1
我们来找最大值。

1
2
3
4
5
if(A[i]>max){
h1=h2;
h2=max;
max = A[i];
}

第一轮
A[0] > max(当前是MIN_VALUE)
h1取h2的值(当前是MIN_VALUE),
h2取max的值(当前是MIN_VALUE),
max取A[i] (当前是-1)

第二轮
A[1] > max(当前是-1)
h1取h2的值(当前是MIN_VALUE),
h2取max的值(当前是-1),
max取A[i] (当前是4)

第三轮
A[2] < max(当前是4)

第四轮,第五轮,已经无需再写了,我们的最大值已经找到了。
if也进不去了。

他这里这个变量名取的不太好,容易让人误解。
感兴趣可以分析一下这个过程,以后要是有类似的要挑选最大,第二大,最小,第二小的题,就可以直接用这个方法啦。

五. 总结

今天是2019 年情人节,上午起的很晚,刷了这道题之后就中午吃饭了,下午朋友叫我出去玩,本身要写本文的也搁置了,直到晚上才写完。

考研这几天也要下成绩了,估计考的也不好,没抱太大希望。
多刷刷算法题,涨涨知识吧。
反正复试和找工作都需要算法。

加油!
无论如何,都相信自己可以的!