解决三个数组元素的最大积,无需排序

Question

有多种的MaxProductOfThree任务答案codility.com,其中大部分涉及排序算法.

问题是:

给出了由N个整数组成的非空零索引数组A.

问题是找到给定数组中3个元素的最大乘积.

阵列的长度在3到100,000之间

数组A的每个元素都是[-1,000..1,000]范围内的整数

    expected worst-case time complexity is O(N*log(N));

    expected worst-case space complexity is O(1), 

超出输入存储(不计入输入参数所需的存储).例:

  a[0] = -3;
  a[1] = 7;
  a[2] = 2;
  a[3] = 1;
  a[4] = 5;
  a[5] = 7;

最大乘积是[1]*a [4]*a [5] = 245

除了涉及排序的O(n log n)方法之外,是否存在线性时间解决该问题的方法？

Answer 1

/*    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. Here is the java code:*/

    int solution(int[] a) {
/* the minimums initialized with max int to avoid cases with extreme max in array and false minims 0 minimums returned */

        int min1 = 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 */

        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

            if (a[i] > max1) {
            //if a[i] is greater than the biggest max then a chain reaction is started,
            // max3 will be max2, max2 will be actual max1 and max1 will be a[i]    
                max3=max2;
                max2=max1;
                max1=a[i];
/* 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 for the max2 amd max3 */

            }else if(a[i]>max2){
                max3 = max2;
                max2 = a[i];
/* finally if current array value isn't bigger than max1 and max2 maybe is greater than 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. */

            if (a[i] < min1) {
                min2 =min1;
                min1=a[i];
            } 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. */

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

//here we just return the biggest product

        return prod1 > prod2 ? prod1 : prod2;

    } 

Answer 2

在排序数组中，最大乘积只有两个可能的选项。

1）最大（最后）三个元素

2）两个最小和最大元素的组合（在负元素的情况下，两个负元素的乘积为正，乘以数组的最大元素（如果为正，则可以产生最大乘积））

因此，解决方案是两者中的最大值，仅此而已。以下在Codility上获得100/100。

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.util.Arrays;

class Solution {

    public int solution(int[] A) {

        int N = A.length;
        Arrays.sort(A);

        /**
         * When we sort an array there are two possible options for the largest product
         * 1) The largest (the last) three elements
         * 2) Combination of two smallest and the largest elements
         * Logic of (1): Obvious
         * Logic of (2): A pair of negatives multiplied returns a positive, which in combination with 
         * the largest positive element of the array can give the max outcome.
         * Therefore we return the max of options (1) and (2)
         */
        return Math.max(A[0] * A[1] * A[N - 1], A[N - 1] * A[N - 2] * A[N - 3]);
    }
}

干杯