无序数组中,三个数的乘积最大

给定一个无序数组,包含正数、负数和0,要求从中找出3个数的乘积,使得乘积最大,要求时间复杂度:O(n),空间复杂度:O(1)

输入,一个无序数组长度n,接着n个数

4
3 4 1 2

输出,最大的结果

24

ac1:(时间复杂度 O(nlogn) ,用到了排序,不符合O(n)的要求)

需要排序,然后根据数据内容计算最大乘积,
注意数据使用 long long , 而非int

#include cstdio  
#include cstdlib  
#include cstring    
#include string
#include vector
#include map
#include cmath
#include iostream
#include queue
#include map
#include set
#include stack
#include list
#include sstream
#include algorithm

using namespace std;

const int INF = 0x7fffffff;

typedef long long int LL;

bool cmp(LL a, LL b)
{
    return a  b;
}

int main()
{
    freopen("in.txt", "r", stdin);
    vectorLL v;

    int  n;
    scanf("%d", n);

    int zCnt = 0;
    int pCnt = 0;
    int nCnt = 0;
    for (int i = 0; i  n;i++)
    {
        LL tmp;
        scanf("%lld", tmp);
        if (tmp  0){
            pCnt++;
        }
        else if (tmp == 0){
            zCnt++;
        }
        else{
            nCnt++;
        }
        v.push_back(tmp);
    }

    //sort(v.begin(), v.begin() + 3, cmp);
    sort(v.begin(), v.end(), cmp);

    LL ans = 0;
    if (nCnt == 0) // 正数和0
    {
        ans = v[0] * v[1] * v[2];
    }
    else if (pCnt == 0)  // 负数和0
    {
        ans = v[0] * v[1] * v[2];
    }
    else if (zCnt = n -2){ // 一正一负,两个正,两个负, ...
        ans = v[0] * v[n - 2] * v[n - 1];
    }
    else{
        // 三个正, 一正两负
        LL val1 = v[0] * v[1] * v[2];
        LL val2 = v[0] * v[n - 2] * v[n - 1];
        ans = max(val1, val2);
    }
    cout  ans  endl;
    return 0;
}
最新回复(0)
/jishuqY6Ay9fD5vd6ADaEFqcMEilnLQQH1TCZNMidRhr5Xys_3D4858215
8 简首页