首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >不排序求解三个数组元素的最大乘积

不排序求解三个数组元素的最大乘积
EN

Stack Overflow用户
提问于 2014-05-06 14:28:11
回答 15查看 9.5K关注 0票数 9

codility.com上的MaxProductOfThree任务有多种答案,其中大多数都涉及排序算法。

问题是:

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

问题是从给定的数组中找出3个元素的最大乘积。

数组的长度在3到100,000之间

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

代码语言:javascript
复制
    expected worst-case time complexity is O(N*log(N));

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

超出输入存储空间(不包括输入参数所需的存储空间)。示例:

代码语言:javascript
复制
  a[0] = -3;
  a[1] = 7;
  a[2] = 2;
  a[3] = 1;
  a[4] = 5;
  a[5] = 7;

最大乘积为a1*a4*a5 = 245

除了涉及排序的O(n log n)方法外,这个问题是否有线性时间解决方案?

EN

回答 15

Stack Overflow用户

回答已采纳

发布于 2014-05-12 20:26:39

代码语言:javascript
复制
/*    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;

    } 
票数 20
EN

Stack Overflow用户

发布于 2018-11-05 05:41:34

对于排序数组中的最大乘积,只有两个可能的选项。

1)最大的(最后)三个元素

2)两个最小和最大元素的组合(对于负元素,两个负数的乘积是正的,乘以一个数组的最大元素,如果是正的,则产生最大的乘积)

因此,解决方案是两个中的最大值,而不是其他。下面的代码是100/100。

代码语言:javascript
复制
// 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]);
    }
}

干杯

票数 12
EN

Stack Overflow用户

发布于 2018-06-05 06:26:05

在这里,它不使用排序,仍然是100%。

代码语言:javascript
复制
#include<limits>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int solution(vector<int> &A) {
    //Keep the absolute value for max 2 -ve num . As their mul will be +ve
    int abs1 = numeric_limits<int>::min();
    int abs2 = numeric_limits<int>::min();

    //Keep the max three num irrespective of sign
    int max1 = numeric_limits<int>::min();
    int max2 = numeric_limits<int>::min();
    int max3 = numeric_limits<int>::min();

    unsigned int size = A.size()-1;

    for (unsigned int i = 0; i <= size ; ++i) {
        if(A[i] > 0 ){

        } else if(abs(A[i]) >= abs1 ) {
            abs2 = abs1;
            abs1 = abs(A[i]);
        }else if(abs(A[i]) >= abs2 ) {
            abs2 = abs(A[i]);
        }

        if(A[i] >= max1 ){
            //Push max1s prev value to max2 and max2's prev val to max3
            max3 = max2;
            max2 = max1;
            max1 = A[i];
        } else if(A[i] >= max2 ) {
            max3 = max2;
            max2 = A[i];
        }else if(A[i] > max3 ) {
            max3 = A[i];
        }
    }
    // Either max 3 multiplication , or Max 2 negative num whose mul is +ve and the regular max
    return max(max1 * max2 * max3, abs1 * abs2 * max1);
}


int main(){
    vector<int> test = {-3, 1, 2, -2, 5, 6};
    cout << solution(test);
    return 0;
}
票数 2
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/23487381

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档