2019-02-14 最大乘积 - 2018拼夕夕校招
这道题目来自 2018年拼夕夕的校招，我从牛客网上刷到这个题。
https://www.nowcoder.com/practice/5f29c72b1ae14d92b9c3fa03a037ac5f
题目可以自行去看，我这里再简单提一下。
一. 题目
给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)
示例如下。
image.png
二.分析
先简单提一下：
以前刷LeetCode是直接写方法，现在用牛客这个在线编译器还不太习惯。
首先我是用java写的，牛客这里的java代码，会要求写一个Main类，然后写main方法，其次，输入是需要写从控制台读取，输出是运算结果，所以读取数据是需要自己写的。
再就是java要导包，其实记几个重要的包就可以满足了。
千万不要以为java 可以这么写：
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。
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大佬的实现。
/**
* 思路：三个数乘积最大，那么肯定包含其中最大的数，然后就只要比较最小的两个数乘积和第二第三大的两个数乘积。
* 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
我们来找最大值。
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 年情人节，上午起的很晚，刷了这道题之后就中午吃饭了，下午朋友叫我出去玩，本身要写本文的也搁置了，直到晚上才写完。
考研这几天也要下成绩了，估计考的也不好，没抱太大希望。
多刷刷算法题，涨涨知识吧。
反正复试和找工作都需要算法。
加油！
无论如何，都相信自己可以的！
