題目描述
思路：
去掉數(shù)組中只有3個數(shù)的特殊情況廓握。如果數(shù)組只有3個數(shù)鸿市，直接將這三個數(shù)的乘積輸出。
去除特殊情況之后徙硅，我最開始的想法是對數(shù)組進(jìn)行排序榜聂，然后如果負(fù)數(shù)的個數(shù)少于等于1個，輸出最大的三個數(shù)的乘積嗓蘑；如果負(fù)數(shù)的個數(shù)大于等于2個须肆，比較最小的兩個負(fù)數(shù)與最大的數(shù)的乘積和最大的3個數(shù)的乘積的大小，輸出大的那個桩皿。代碼如下：
import java.util.Arrays;
class Solution {
public int maximumProduct(int[] nums) {
int res = 1;
int length = nums.length;
if (length == 3) {
res = nums[0] * nums[1] * nums[2];
} else {
Arrays.sort(nums);
if (nums[0] >= 0 || (nums[0] < 0 && nums[1] >= 0)) {
res = nums[length - 1] * nums[length - 2] * nums[length - 3];
} else {
int temp1 = nums[0] * nums[1] * nums[length - 1];
int temp2 = nums[length - 1] * nums[length - 2] * nums[length - 3];
res = temp1 > temp2 ? temp1 : temp2;
}
}
return res;
}
}
執(zhí)行用時: 14 ms（超過9.084%）
內(nèi)存消耗: 40.3 MB
效果不好豌汇，細(xì)想一下，反正也只需要最小的兩個數(shù)和最大的三個數(shù)泄隔。那么可以對數(shù)組遍歷5次拒贱，找出這5個數(shù)就好了。
那么又有一個問題梅尤，如果數(shù)組中元素個數(shù)少于5個柜思？我也懶得考慮太多的情況。于是對之前的代碼進(jìn)行復(fù)用巷燥，當(dāng)數(shù)組元素個數(shù)較少時使用之前的方法赡盘。最終的代碼如下：
import java.util.Arrays;
class Solution {
public int maximumProduct(int[] nums) {
int res = 1;
int length = nums.length;
if (length == 3) {
res = nums[0] * nums[1] * nums[2];
} else if (length <= 32) {
Arrays.sort(nums);
if (nums[0] >= 0 || (nums[0] < 0 && nums[1] >= 0)) {
res = nums[length - 1] * nums[length - 2] * nums[length - 3];
} else {
int temp1 = nums[0] * nums[1] * nums[length - 1];
int temp2 = nums[length - 1] * nums[length - 2] * nums[length - 3];
res = temp1 > temp2 ? temp1 : temp2;
}
} else {
int temp = 0;
int count = 0;
while (count < 5) {
if (count % 2 == 0) {
// find the max
for (int i = 0; i < length - 1; i++) {
if (nums[i] > nums[i + 1]) {
temp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = temp;
}
}
} else {
// find the min
for (int j = length - 2; j >= 0; j--) {
if (nums[j] > nums[j + 1]) {
temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
count++;
}
int temp1 = nums[0] * nums[1] * nums[length - 1];
int temp2 = nums[length - 1] * nums[length - 2] * nums[length - 3];
res = temp1 > temp2 ? temp1 : temp2;
}
return res;
}
}
執(zhí)行用時: 4 ms（超過74.109%）
內(nèi)存消耗: 40 MB
還行，思路也跟官方題解一樣缰揪。
