2019年5月25日
写在开头第一题我自己的想法正确的想法（参考dong1234的）完整代码
写在开头
学着写博客的第一天！距离秋招还有3个多月，最近在疯狂找实习，通过写博客来记录每天的学习内容。
我一定能当个码农！！！
第一题
最大乘积问题 题目描述：给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)。
我自己的想法
就是将输入的数组进行排序，然后最大的乘积是正数的最大三个数的乘积或者是最小的两个负数和一个最大正数的乘积。 这个想法存在的问题有： （1）少考虑一种情况：就是全都是负数的时候 （2）题目中要求的时间复杂度为O(N)，而排序数组的最小复杂度为O(NlogN)，所以不可行。
正确的想法（参考dong1234的）
首先，最大的数只可能是数组中最大的三个数的乘积或者是最小的两个数和最大的一个数的乘积。 因此，我们只需要遍历数组找出最大的三个数(max1,max2,max3)和最小的两个数(min1,min2)即可。
接着，我们需要考虑的问题就是如何在不排序数组的前提下找出上述的几个值。 （1）第一步，for循环遍历数组 （2）第二步，找出最大的三个数：如果数组的其中的元素大于max1，这时这个元素就是最大的，次大的元素就是max1，次次大的元素就是max2。 注意：赋值的时候首先把max3=max2,max2=max1，再把max1=元素。这里我把它顺序搞反了，没得到正确的结果！可惜，可惜！！！ (3)第三步，找两个最小的数：同理！
然后，话不多说，上代码！
for(int i=0;i<len;i++) {
if(arr[i]!=0) {
if(arr[i]>max1) {
max3=max2;
max2=max1;
max1=arr[i];
}else if(arr[i]>max2) {
max3=max2;
max2=arr[i];
}else if(arr[i]>max3) {
max3=arr[i];
}else if(arr[i]<min1) {
min2=min1;
min1=arr[i];
}else if(arr[i]<min2) {
min2=arr[i];
}
}else
continue;
}
最后，找最大值的时候记得运用Math.max（）方法！
完整代码
import java.util.Scanner;
//遍历数组时记录第一，第二，第三和最小，次小的数
public class mianshiti1 {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int len = scan.nextInt();
long[] arr = new long[len];
for (int i = 0; i < len; i++) {
arr[i] = scan.nextLong();
}
long max;
max = getMax(arr, len);
System.out.print(max);
}
private static long getMax(long[] arr, int len) {
// TODO Auto-generated method stub
long max1 = 0, max2 = 0, max3 = 0;
long min1 = 0, min2 = 0;
// 遍历数组
for (int i = 0; i < len; i++) {
if (arr[i] != 0) {
if (arr[i] > max1) {
max3 = max2;
max2 = max1;
max1 = arr[i];
} else if (arr[i] > max2) {
max3 = max2;
max2 = arr[i];
} else if (arr[i] > max3) {
max3 = arr[i];
} else if (arr[i] < min1) {
min2 = min1;
min1 = arr[i];
} else if (arr[i] < min2) {
min2 = arr[i];
}
} else
continue;
}
long max = Math.max(max1 * max2 * max3, max1 * min1 * min2);
return max;
}
}
