题目

描述

• 给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：，空间复杂度：。

方法一

思路

求一个数组中的三数最大乘积，且包括负数，所以需要考虑两种情况：

• 两个最小负数，一个最大正数
• 三个最大正数
  所以只需要对其进行升序排序，取这两种情况中最大值即可。

具体步骤

• 通过JDK自带的Array.sort对数组进行升序排序；
• 计算两种情况各自的乘积
• 代码如下：

  import java.util.*;
  public class Solution {
  /**
  * 最大乘积
  * @param A int整型一维数组 
  * @return long长整型
  */
  public long solve (int[] A) {
     // 升序排序
     Arrays.sort(A);
     return Math.max((long)A[0]*A[1]*A[A.length-1],
                     (long) A[A.length-1] * A[A.length-2] * A[A.length-3]);
  }
  }

• 时间复杂度：，JDK的Array.sort函数的时间复杂度为；
• 空间复杂度：，常数级空间复杂度。

方法二

思路

方法一的时间复杂度为，但是题目要求的是，显然方法一是无法满足要求的，而排序的时间复杂度基本上都在以上，当然使用线性的排序方法也可以；不过这里考虑到题目只是要求找出前三大以及前二小的数值，所以可以遍历一遍数组，将这几个数直接找出来。

具体步骤

• 见下图例子
  
  
• 代码如下：

import java.util.*;
public class Solution {
/**
* 最大乘积
* @param A int整型一维数组 
* @return long长整型
*/
public long solve (int[] A) {
   // 最大的第二大的和第三大的
   int[] maxNums = new int[]{Integer.MIN_VALUE,Integer.MIN_VALUE,Integer.MIN_VALUE};
   //最小的和第二小的（负数的时候要用）
   int[] minNums = new int[]{Integer.MAX_VALUE,Integer.MAX_VALUE};
   for(int i = 0;i < A.length;i ++){
       if(A[i] < minNums[0]){//更新最小值
           minNums[1] = minNums[0];
           minNums[0] = A[i];
       }else if(A[i] < minNums[1]){//更新第二小
           minNums[1] = A[i];
       }
       if (A[i] > maxNums[0]){//更新最大值
           maxNums[2] = maxNums[1];
           maxNums[1] = maxNums[0];
           maxNums[0] = A[i];
       }else if(A[i] > maxNums[1]){//更新第二大
           maxNums[2] = maxNums[1];
           maxNums[1] = A[i];
       }else if(A[i] > maxNums[2]){//更新第三大
           maxNums[2] = A[i];
       }
   }
   long a = (long)minNums[0] * minNums[1] * maxNums[0];
   long b = (long)maxNums[0] * maxNums[1] * maxNums[2];
   return Math.max(a,b);
}
}

• 时间复杂度：，遍历一遍数组，n；
• 空间复杂度：，只是使用了5个变量，所以为常数级空间复杂度。