LeetCode：1.最大乘积

Leetcode :数组
Diffculty：空间复杂度 / 数组 / long

---

题目：

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

输入描述:

输入共2行，第一行包括一个整数n，表示数组长度
第二行为n个以空格隔开的整数，分别为A1,A2, … ,An

输出描述:

满足条件的最大乘积

去最大乘数有两种可能，两负一正和三正（还有个为意外情况得0），然后两个对比取最大，所以需要取出前三大的正数和前二小的负数，每一轮for循环可以同时取最大正数和最小负数，所以代码做了三轮（第一轮顺便度数）。

具体优化：
因为java默认数组在内存中就是线性表，所以用索引做唯一表达最好，而不是将已选中的数字取出。3轮循环并不比一遍循环取出所有数据差，因为如果一遍，每次内部几个数字还是要进行三次比较。

下面上代码：

import  java.util.Scanner;
 
public class Main{
  
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n =sc.nextInt();
        long [] arr=new long[n];
        int [] maxSe={-1,-1,-1};
        int [] minSe={-1,-1};
        long [] max=new long[3];
        long [] min=new long[2];
        int i=0;
        for(i=0;i<n;i++){
            arr[i]=sc.nextLong();//输入数字
            if(arr[i]>=0&&arr[i]>max[0]){//取第一大第一小
                max[0]=arr[i];
                maxSe[0]=i;
            }
            else if(arr[i]<0&&arr[i]<min[0]){
                min[0]=arr[i];
                minSe[0]=i;
            }
        }
        for(i=0;i<n;i++){//第二轮取第二大第二小
             if(arr[i]>=0&&arr[i]>max[1]&&i!=maxSe[0]){
                max[1]=arr[i];
                maxSe[1]=i;
            }
            else if(arr[i]<0&&arr[i]<min[1]&&i!=minSe[0]){
                min[1]=arr[i];
                minSe[1]=i;
            }
             
        }
        for(i=0;i<n;i++){//取第三大
            if(arr[i]>=0&&arr[i]>max[2]&&i!=maxSe[0]&&i!=maxSe[1]){
                max[2]=arr[i];
                maxSe[2]=i;
            }
        }
      long maxnumber=Math.max(max[0]*max[1]*max[2],max[0]*min[0]*min[1]);
      System.out.println( maxnumber);
    }
}

第二种解题思路：（下面代码）

import java.util.Scanner;
public class Main{
    public static void main(String args[]){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        long nums[]=new long[n];
        for(int i=0;i < n;i++){
            nums[i] = scan.nextInt();
        }
        System.out.println(maxTriMultiply(nums));
    }
    /**
     *  思路：三个数乘积最大，那么肯定包含其中最大的数，然后就只要比较最小的两个数乘积和第二第三大的两个数乘积。
     *  m1,m2是最小的两个数，max,h2,h1为第一/二/三大的数
     */
    public static long maxTriMultiply(long A[]){
        long m1 = Integer.MAX_VALUE, m2 = Integer.MAX_VALUE, h1 = Integer.MIN_VALUE, h2 = Integer.MIN_VALUE, max = Integer.MIN_VALUE;
        for(int i=0;i < A.length;++i){
            if(A[i]>max){
                h1=h2;
                h2=max;
                max = A[i];
            }else if(A[i]>h2){
                h1=h2;
                h2 = A[i];
            }else if(A[i]>h1){
                h1=A[i];
            }
            if(A[i] < m1){
                m2=m1;
                m1=A[i];
            }else if(A[i] < m2)
                m2=A[i];
        }
        max = max * m1 * m2 > max * h1 * h2 ? max * m1 * m2 : max * h1 * h2;
        return max;
    }
}

该题主要是时间和空间的要求，所以排序不可取， 但可以借鉴排序的思想。首先计算n个数中正数、负数和0的个数。
乘积为正肯定最大，有两种情况：1 有三个正数相乘， 2 有两负一正 ，取两种情况的最大者即可
否则，若有0 则返回0，没有的话，继续
负数分两种情况 1 三个负数 ，寻找最大的三个负数即可 。 2 一负两正 ，取两最小的正数和一最大的负数 ，返回两种情况最大的即可
在选取的时候 ，可用选择排序方法

第三种解题思路：（下面代码）

需要注意的是接收参数的时候要用long类型的

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        List<Long> list=new ArrayList<>();
        int k=scanner.nextInt();
        for(int i=0;i<k;i++)
        {
            list.add(scanner.nextLong());
        }
        if(list.size()==3)
        {
            //如果只有三个数直接输出
            System.out.println(list.get(0)*list.get(1)*list.get(2));
            return;
        }
        //从大到小排序
        Collections.sort(list);
        int length=list.size()-1;
        //如果第一个数大于等于0或者最后一个数小于等于0，则直接输出最后三个数乘积
        if(list.get(0)>=0||list.get(length)<=0)
        {
            System.out.println(list.get(length)*list.get(length-1)*list.get(length-2));
            return;
        }
        //如果第一个数小于0且第二个数大于等于0，即只有一个负数，则直接输出最后三个数乘积
        if(list.get(0)<0&&list.get(1)>=0)
        {
            System.out.println(list.get(length)*list.get(length-1)*list.get(length-2));
            return;
        }
        //如果第一个数第二个数都小于0，即有两个或两个以上的负数，则需要比较（最后三个数乘积） 和 （第一个数第二个数和最后一个数乘积）大小，取大的
        if(list.get(0)<0&&list.get(1)<0)
        {
             
            long m=list.get(length)*list.get(length-1)*list.get(length-2);
            long n=list.get(0)*list.get(1)*list.get(length);
            if(m>n)
            {
                System.out.println(m);
            }
            else
            {
                System.out.println(n);
            }
            return;
        }
    }
 
}