一个给定数组大小为N的三个数字的最大乘积。

I need to write a program to find the Max product of three numbers for a given array of size N. Is there any effective algorithm for this? I just need to know the algorithm steps. Non of algorithms that i thought works for all the test cases. Thanks! FYI Array may contains +ve, -ve, or zero elements)

我需要编写一个程序来找出一个给定数组大小的三个数字的最大乘积。有什么有效的算法吗?我只需要知道算法步骤。非算法我认为适用于所有测试用例。谢谢!FYI数组可以包含+ve -ve或0元素)

8 个解决方案

#1

Find the three largest numbers in the array (n1, n2, n3) and the two smallest numbers (m1, m2).

找到数组中三个最大的数字(n1, n2, n3)和两个最小的数字(m1, m2)。

The answer is either n1 x n2 x n3 or n1 x m1 x m2

答案要么是n1 x n2 x n3，要么是n1 x m1 x m2

#2

The method get the max product of 3 consists in basically find the biggest 3 numbers from the array and the smallest 2 numbers from the array in just 1 iteration over the array. There are of course a large variety of solutions but this is the optimal 1 because the time to solve the problem is O(n), the other solutions time is O(n lg n)

得到3的最大乘积的方法主要包括从数组中找到最大的3个数字，从数组中找到最小的2个数字。当然有很多种解但这是最优解因为解这个问题的时间是O(n)其它解的时间是O(n lgn)

Here is the java code: by the way there is a guarantee that the input array is non empty and contains minimum 3 elements so there is no need to extra checks for empty and so on.

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

  int solution(int[] a) {

/* the minimums initialized with max int to avoid cases with extreme max in array and false minims 0 minimums returned */

/*使用max int初始化的最小值，以避免数组中最大值的情况出现，返回错误的最小值为0 */

int min1 = Integer.MAX_VALUE;

int min1 = Integer.MAX_VALUE;

int min2 = Integer.MAX_VALUE;

int min2 = Integer.MAX_VALUE;

/* the same logic for maximum initializations but of course inverted to avoid extreme minimum values in array and false 0 maximums */

/*最大初始化的逻辑是相同的，但当然是反向的，以避免数组中的极端最小值和假的0最大值*/

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

//the iteration over the array

//对数组的迭代

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

//test if max1 is smaller than current array value

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

        if (a[i] > max1) {

/* store the max1 current value in a temp var to test it later against the second maximum here as you can see is a chain of changes if is changed the biggest max we must change the other 2 */

/*将max1当前值存储在temp var中，以便稍后在这里测试第二个最大值，因为您可以看到，如果更改最大的最大值，我们必须更改另一个2 */。

            int tempMax1 = max1;

//assign the current array value as maximum

//指定当前数组的值为最大值

            max1=a[i];

//test tempMax1 former max1 value against max2

//对max2测试tempMax1前max1值

            if(tempMax1>max2){

/* store max2 value in tempMax2 value to test it against max3 and assign it to max 3 if it's bigger */

/*在tempMax2值中存储max2值，以测试max3，并将其分配给max3，如果它更大*/。

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

/* test to see if tempMax1 is bigger if isn't bigger than max3, this is happening when max1 gets a new value and the old value of max1 is equal with max2 but bigger than max3 */

检验tempMax1是否大于max3，当max1获得一个新值，max1的旧值与max2相等但大于max3 */时发生

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

/* in case if current a[i] isn't bigger than max1 we test it to see maybe is bigger than second max. Then the same logic from above is applied here to max3 */

/*如果电流a[i]不大于max1，我们测试它，看它是否大于第二个max。然后，同样的逻辑从上面应用到这里的max3 */

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

/* finally if current array value isn't bigger than max1 and max2 maybe is greater than max3 */

/*最后，如果当前数组值不大于max1, max2可能大于max3 */

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

/* The logic from above with maximums is is applied here with minimums but of course inverted to discover the 2 minimums from current array. */

/*上面的带有最大值的逻辑在这里用最小值来应用，但是当然是反向的，以发现当前数组中的2个最小值。* /

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

/* after we discovered the 3 greatest maximums and the 2 smallest minimums from the array we do the 2 products of 3 from the greatest maximum and the 2 minimums . This is necessary because mathematically the product of 2 negative values is a positive value, and because of this the product of min1 * min2 * max1 can be greater than max1 * max2 * max3 and the product built from the the 3 maximums. */

/*在我们发现数组中最大的3个最大值和最小的2个最小值之后，我们从最大的3和2个最小值得到2个乘积。这是必要的，因为从数学上来说，2个负值的乘积是一个正值，因此min1 * min2 * max1的乘积可以大于max1 * max2 * max3，而product是根据3个最大值构建的。* /

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

//here we just return the biggest product

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

    return prod1 > prod2 ? prod1 : prod2;

}

#3

Given an array of list = (n1, n2, n3...). You can do this in 3 passes.

给定一个列表数组= (n1、n2、n3…)。你可以用3次传递。

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

Now a1*a2 is either positive, negative or zero. If zero then there are many solutions; pick any n_i from the rest of the numbers. If a1*a2 > 0 then pick the largest positive number otherwise smallest negative number. More succinctly, you can just make one pass through the rest of the list:

a1*a2要么是正的，要么是负的，要么是零。如果为0，则有许多解;从剩下的数字中选择任何一个n_i。如果a1*a2 >，那么选择最大的正数，否则选择最小的负数。更简洁地说，你可以让一个人通过列表的其余部分:

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

#4

This is a good solution in Java:

这是一个很好的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;

    }
}

#5

Not an efficient solution, but a useful backup to show the use of data structures. Create a max heap and min heap out of these integers. Then delete the root from max heap till you get 3 distinct integers (top 3) and get the least two distinct integers from the min heap. Do the rest of the checks as mentioned in other responses max (max1 * max2 * max3, max1, min1, min2)

这不是一个有效的解决方案，而是显示数据结构使用的有用备份。从这些整数中创建最大堆和最小堆。然后从最大堆中删除根，直到得到3个不同的整数(前3个)，并从最小堆中获得至少两个不同的整数。执行其他响应max (max1 * max2 * max3、max1、min1、min2)中提到的其他检查

#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

#7

I Wrote this simple solution in Python which I was looking and could't find.

我用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)

#8

Please use a BubbleSort procedure and break within three iterations. Take the bottom of three and multiply. That should provide you the solution.

请在三个迭代中使用BubbleSort程序和中断。把3的底乘起来。这将为您提供解决方案。

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];