对于给定数组大小为N的三个数的最大乘积

Question

我需要编写一个程序来查找给定数组大小为N的三个数的最大乘积。 有没有对此有效的算法？ 我只需要知道算法步骤。非我认为适用于所有测试用例的算法。 谢谢！ FYI数组可包含+ ve，-ve或零元素）

Answer 1

查找数组中的三个最大数字（n1，n2，n3）和两个最小数字（m1，m2）。

答案是要么N1 X N2 N3 X或N1 X M1 X平方米

Answer 2

给定列表的阵列=（N1，N2，N3 ...）。你可以通过3次。

Let a1 = max (|n_i|) 
Let a2 = max (|n_i|) where n_i != a1 

现在a1 * a2是正数，负数或零。如果为零，那么有很多解决方案;从其余的数字中挑选任何n_i。如果a1 * a2> 0，则选择最大的正数，否则选择最小的负数。更简洁地说，你可以做一次通过列表的其余部分：

Let max_product = max (a1*a2*n_i) where n_i != a1 or a2 

Answer 3

的方法得到的3最大的产品包括在基本找到该数组中最大的3个号码，最小的2号从数组在数组中只需要1次迭代。当然有很多种解决方案，但这是最优的1，因为解决问题的时间是O（n），其他解决方案时间是O（n lg n）

这里是java代码： 顺便说一句，有一个保证，输入数组是非空的，并且包含最少3个元素，所以不需要额外检查空等等。

int solution(int[] a) { 

/*与最大INT初始化以避免在阵列和假量滴极端最大值情况下，最小值0最小值返回*/

INT MIN1 = Integer.MAX_VALUE的;

int min2 =整数。MAX_VALUE;

/*为最大初始化但当然反转，以避免在阵列极端最低值的相同的逻辑和假0最大值*/

int max1 = Integer.MIN_VALUE; 
    int max2 = Integer.MIN_VALUE; 
    int max3 = Integer.MIN_VALUE; 

//迭代阵列之上

for (int i = 0; i < a.length; i++) { 

//测试max1是否小于当前数组值

 if (a[i] > max1) { 

/*存储m在一个临时的无功电流AX1值来测试它后来对第二最大 在这里，你可以看到的是变化的链条，如果改变了我们必须改变，另2 */

  int tempMax1 = max1; 

//分配最大最大当前数组值作为针对MAX2最大值

  max1=a[i]; 

//测试tempMax1前MAX1值

  if(tempMax1>max2){ 

/*存储在MAX2值tempMax2值来测试它AG如果它是更大的ainst MAX3并将其分配给最多3 */

   int tempMax2 = max2; 
       max2 =tempMax1; 
       if(tempMax2>max3){ 
        max3 = tempMax2; 
       } 

/*测试，看看tempMax1较大，如果不大于MAX3大，当 MAX1得到一个新值与旧这种情况正在发生MAX1的值等于与MAX2但大于MAX3 */

  }else{ 
       if(tempMax1>max3){ 
        max3 = tempMax1; 
       } 
      } 

在壳体/ *如果当前一个[i]为不大于MAX1更大我们进行测试，看看也许比第二 最大值更大。然后，从上述相同的逻辑，这里应用于MAX3 */

 }else if(a[i]>max2){ 
      int tempMax2 = max2; 
      max2 = a[i]; 
      if(tempMax2>max3){ 
       max3 =tempMax2; 
      } 

/*最后如果当前数组值不大于MAX1和MAX2大也许比MAX3更大*/

 }else if(a[i]>max3){ 
      max3 = a[i]; 
     } 

/*上面的逻辑与最大值是在这里应用最小值，但当然反转到 发现当前数组的2个最小值。 */

 if (a[i] < min1) { 
      int tempMin1 = min1; 
      min1 = a[i]; 
      if (tempMin1 < min2) { 
       min2 = tempMin1; 
      } 
     } else if (a[i] < min2) { 
      min2 = a[i]; 
     } 
    } 

/*后，我们发现从阵列 3个最大的最大值和2个最小的最小值，我们做了2个产品3从最大的最大值和最小值2。这是必要的 ，因为在数学上2个负值的乘积是正值，并且因为min1 * min2 * max1的乘积可以大于max1 * max2 * max3 以及由3个最大值构建的乘积。*/

int prod1 = min1 * min2 * max1; 
    int prod2 = max1 * max2 * max3; 

//这里我们只返回最大的产品

return prod1 > prod2 ? prod1 : prod2; 

} 

Answer 4

这是Java中的一个很好的解决方案：

class Solution { 
    public int solution(int[] A) { 
     int result1, result2; 

     Arrays.sort(A); 
     result1 = A[0] * A[1] * A[A.length-1]; 
     result2 = A[A.length-1] * A[A.length-2] * A[A.length-3]; 

     if (result1 >= result2) return result1; 
     else return result2; 

    } 
} 

Answer 5

不是一个有效的解决方案，但一个有用的备份显示数据结构的使用。从这些整数中创建一个最大堆和最小堆。然后从max堆中删除根，直到获得3个不同的整数（前3），并从min堆中获取至少两个不同的整数。做检查的其余部分作为最大其他应答（MAX1 * MAX2 * MAX3，MAX1，MIN1，MIN2）

Answer 6

def max_three_product(a): 
a=sorted(a) 
max_prod=a[-1]*a[-2]*a[-3] 
if a[0]>0: 
    return a[-1]*a[-2]*a[-3] 
else: 
    if a[0]*a[1]<0: 
     return max_prod 
    elif a[1]*a[2]>0: 
     if a[0]*a[1]*a[-1]>max_prod: 
      return a[0]*a[1]*a[-1] 
     else: 
      return max_prod 
    else: 
     if a[0]*a[1]*a[-1]>max_prod: 
      return a[0]*a[1]*a[-1] 
     else: 
      return max_prod 

Answer 7

提到我写在Python这种简单的解决方案，我一直在寻找和发现便无法。

def ThreeHighestNumbers(arrayOfNumbers): 
    PmaxNum1 = 0 
    PmaxNum2 = 0 
    PmaxNum3 = 0 
    NMinNum1 = 0 
    NMinNum2 = 0 
    maxNumber = 0 

    for num in arrayOfNumbers: 
     if num < 0: 
      if num < NMinNum1: 
       NMinNum2 = NMinNum1 
       NMinNum1 = num 
      elif num < NMinNum2: 
       NMinNum2 = num 
     else: 
      if num > PmaxNum1: 
       PmaxNum3 = PmaxNum2 
       PmaxNum2 = PmaxNum1 
       PmaxNum1 = num 

      elif num > PmaxNum2: 
       PmaxNum3 = PmaxNum2 
       PmaxNum2 = num 

      elif num > PmaxNum3: 
       PmaxNum3 = num 

    maxNumber = PmaxNum1 * PmaxNum2 * PmaxNum3 

    if maxNumber == 0: 
     return [] 

    if maxNumber < PmaxNum1 * NMinNum1 * NMinNum2: 
     return [PmaxNum1,NMinNum2,NMinNum1] 
    else: 
     return [PmaxNum1,PmaxNum2,PmaxNum3] 



arraOfNumbers = [1,2,3,4,5,6,-8,-9,0] 
print ThreeHighestNumbers(arraOfNumbers) 

Answer 8

请使用BubbleSort过程并在三次迭代中中断。取三个的底部并乘。这应该为您提供解决方案。

int count = 0, j=a.length; 
boolean swap = false; 
do 
{ 
    swap = false; 
    for(int i=1;i<j;i++) 
    { 
    if(a[i]<a[i-1]) 
    { 
     int t= a[i]; 
     a[i] = a[i-1]; 
     a[i-1] = t; 
     swap = true; 
    } 
    } 
    System.out.println(j+" Iteration:"+Arrays.toString(a)); 
    j--; 
    if(swap) 
    count++; 
} while(swap && count<3); 
System.out.println(Arrays.toString(a)); 
return a[a.length-1]*a[a.length-2]*a[a.length-3];