题解 | #三个数的最大乘积#
三个数的最大乘积
http://www.nowcoder.com/practice/8ae05c2913fe438b8b14f3968f64fc0b
1、线性法找5个数字：
时间复杂度O(n)，空间复杂度O（1）
import java.util.*;
public class Solution {
/**
* 最大乘积
* @param A int整型一维数组
* @return long长整型
*/
public long solve (int[] A) {
// write code here
// write code here
// 最小的和第二小的
int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
// 最大的、第二大的和第三大的
int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
for (int x : A) {
if (x < min1) {
min2 = min1;
min1 = x;
} else if (x < min2) {
min2 = x;
}
if (x > max1) {
max3 = max2;
max2 = max1;
max1 = x;
} else if (x > max2) {
max3 = max2;
max2 = x;
} else if (x > max3) {
max3 = x;
}
}
return Math.max((long)min1 * min2 * max1, (long)max1 * max2 * max3);
}
}
2、时间复杂度为sort排序的复杂度，空间复杂度为sort的复杂度
先排序，最小*第二小*最大（两个最小负数的乘积很大的情况）；最大*第二大*第三大