拼多多 面试题 最大成绩

题目描述

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

输入描述:

无序整数数组A[n]

输出描述:

满足条件的最大乘积

示例1

输入

复制

3 4 1 2

输出

复制

24


思路

/定义五个数,一个最大,一个次大,一个第三大,一个最小,一个次小。

只要找到这五个数,问题就解决了。因为最大乘积只可能是

最大(次大第三大) 或者是 最大(最小次小)。时间复杂度O(n),

空间复杂度O(1)。PS:这道题输入有问题,题目给的样例是直接给了一组数,

而此时用例先给了一个数的个数n,然后再给了一组数/


import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long[] array=new long[n];
        for(int i=0;i<n;i++){
            array[i]=sc.nextLong();
        }

        getTheMostValue(array,n);
    }
    
    public static void getTheMostValue(long[] num,int len){
        long max1=0;long max2=0;long max3=0;long min1=0;long min2=0;
        
        for(int i=0;i<len;i++){
            if(num[i]>max1){
                max3=max2;
                max2=max1;
                max1=num[i];
            }else if(num[i]>max2){
                max3=max2;
                max2=num[i];
            }else if(num[i]>max3){
                max3=num[i];
            }else if(num[i]<min1){
                min2=min1;
                min1=num[i];
            }else if(num[i]>min1&&num[i]<min2){
                min2=num[i];
            }
        }
        
        long max=Math.max(max1*max2*max3,max1*min1*min2);
        System.out.println(max);
    }
}
上一篇:Hadoop中通过ToolRunner和Configured实现直接读取命令行动态出入reduce task数量,jar文件等


下一篇:中国人工智能学会通讯——机器学习在商务智能中的创新应用 1.4 为什么要重视非结构化数据