2018 拼多多 校招真题 最大乘积

最大乘积

 

时间限制：1秒 空间限制：32768K 热度指数：8197

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

题目描述

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

输入描述:

无序整数数组A[n]

输出描述:

满足条件的最大乘积

示例1

输入

3 
4 1 2

输出

8


思路分析：

看到这个题目，下意识想到用Arrays.sort()排一下序，

因为输入的整数可以是负数，所以只需要用Math.max()判断一下，

最大的三个数的乘积 与 最小两个数与最大那个数的乘积 哪个数大，输出哪个就行啦，

例如：5,3,2，-8，-9；
5*3*2=30 < 5*(-8)*(-9)=360

but Arrays.sort()的思路是归并排序，时间复杂度是O(n*log(n)),不符合题目要求

所以，额，，，我就用了最最笨的方法哈哈：

我用三个变量存前三大的整数，用两个变量存最小的两个数；

一边接收输入的值，一边判断，时间复杂度为O(n),空间复杂度为O(1);

最后输出 最大的那三个数的乘积大与最小的那两个数与最大的数的乘积中较大的数就ok啦。

Java 代码如下：

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sca = new Scanner(System.in);
        int n = 0;
        int m = sca.nextInt();
        int max=Integer.MIN_VALUE,max1=Integer.MIN_VALUE,max2=Integer.MIN_VALUE,min=Integer.MAX_VALUE,min1 = Integer.MAX_VALUE;
        for(int i = 0;i<m;i++){
            n = sca.nextInt();
           if(max>n){
                   max2 = Math.max(Math.min(max1,n),max2);
                max1 = Math.max(max1,n);
           }else{
                max2 = max1;
                max1 = max;
                max = n;
            }
            if(min<n)
                min1 = Math.min(min1,n);
            else{
                min1 = min;
                min = n;
            }
        }
        long a = (long)max*max1*max2;
        long b = (long)max*min*min1;
        System.out.println(Math.max(a,b));
    }
}