最大的三个数的乘积

2019/04/12 11:24
阅读数 48

最大的三个数的乘积

内容描述:                                                       
给定一个无序数组,包含正数,负数和0,要求从中找出3个数的乘积,
使得乘积最大,要求时间复杂度:O(n),空间复杂度:O(1); 
输入描述:
       无序整数数组A[n]
输出描述:
       满足条件的最大乘积
示例1
输入
3 4 1 2
输出
24
这里需要注意一下的是,题目中的输入格式是 输入数组长度 4 输入数组的每个元素 3 4 1 2 输出 24 问题的之外的一些注意点: 如果给定数组的长度小于3的话,那结果返回是0,还是提示不符合要求。 假设: 所给的数组的长度大于等于3,对于这种情况下,求3个数的最大乘积数。 思路分析: 1.基于暴力枚举的方法:最开始想到的是暴力的方法,3层循环,每一层 获取一个数组的元素,与当前的最大值进行比较,由于有时间复杂度要求, 明显是不可以的。 // 不过这个可以用来对下面方法的结果进行测试。 public long muliptyMax(double[] a) { long sum=a[0]*a[1]*a[2]; for(int i=0;i<a.length;i++) { for(int j=i+1;j<a.length;j++) { for(int k=j+1;k<a.length;k++) { if(sum<a[i]*a[j]*a[k]) sum=a[i]*a[j]*a[k]; } } } return sum; } 2.对结果进行分析,要求三个数的最大乘积可能形式有: 1.无序数组都是正数(包含0),找三个最大的数。 2.无序数组都是负数,仍然是找三个最大的数。 3.有正数(包括0)有负数。可能的形式就是三个正数或者是两负一正。 通过这些结果会发现,只要我们可以保存这几个遍历数组时,可以把对应的 最大的三个正数,二个最小的负数找到,就可以求出三个数的最大乘积了。 细分问题:遍历一次数组怎么实现得到得到最大的三个数和最小的两个数。 从最小的两个数进行分析:我们可以定义两个变量来保存最小负数和次小 负数,遍历数组中的元素时,和当前的这两个变量进行比较。 1.如果当前元素比最小负数小,把最小负数的值赋给次小负数,把当前元素 赋给最小负数。比如:当前元素是-5 ,最小负数是 -4 ,次小负数是 -3 那么比较后就最小负数是 -5 ,次小负数是 -4 2.如果当前元素比最小负数大,但是次小元素小,就当前元素赋给次小元素。 比如:当前元素是-5 ,最小负数是 -6 ,次小负数是 -3 那么比较之后的结果就是 最小负数是 -6 ,次小负数是 -5 注意:基于对两个最小负数的求法,对于两个变量的初始值,就很重要了。 1.一般是使用数组中的元素作为初始值。比如a[0] 但是这样是有问题的(可以解决,相对麻烦,要赋值之前要进行判断) ),使用不在数组范围中的值进行初始化。 使用Integer.MIN_VALUE;Integer.MAX_VALUE赋值。 其实我们不一定要赋值,可以使用下标。 因为下标是唯一的,元素中的数据值可能是重复的。 还有要注意的一点保存数据的范围,用long保存数据,否则会溢出。 二个最小的负数找到,同理可以找到三个最大的整数了。
import java.util.Scanner;
public class ThreeDataMulipty {
    public static int muliptyMax(int[] a)  { 
        // 定义三个变量保存最大的三个数。
        int maxOne=Integer.MIN_VALUE;
        int maxTwo=Integer.MIN_VALUE;
        int maxThree=Integer.MIN_VALUE;
        // 两个最小负数
        int minOne=Integer.MAX_VALUE;
        int minTwo=Integer.MAX_VALUE;
//        System.out.println("每次=maxone:"+maxOne+"maxtwo:"+maxTwo+"maxthree:"+maxThree);
        // 遍历一次数组,将各个合适的元素放到对应的位置。
        for(int i=0;i<a.length;i++)  
        {
          if(maxOne<a[i])  {
             maxThree=maxTwo;
             maxTwo=maxOne;
             maxOne=a[i];
          } else {
             if(maxTwo<a[i])  {
                maxThree=maxTwo;
                maxTwo=a[i];
             } else  {
                if (maxThree<a[i]) {
                  maxThree=a[i];
                }
             }
          }
//          System.out.println("每次=maxone:"+maxOne+"maxtwo:"+maxTwo+"maxthree:"+maxThree);
          // 求两个最小负数。
          if(minOne>a[i])  {
             minTwo=minOne;
             minOne=a[i];
          } else  {
             if(minTwo>a[i]) {
                minTwo=a[i];
             }
          }
         
        }
//        System.out.println(Arrays.toString(a));
//        System.out.println("maxone:"+maxOne+"maxtwo:"+maxTwo+"maxthree:"+maxThree);
//        System.out.println("minone:"+minOne+"mintwo:"+minTwo);
        int maxMulipty=maxOne*maxTwo*maxThree;
        int minMulipty=minOne*minTwo*maxOne;
        return maxMulipty>minMulipty?maxMulipty:minMulipty;
    }
    public static void main(String[] args) {
        Scanner scn=new Scanner(System.in);
// 输入数组长度
int n=scn.nextInt(); int[] a=new int[n];
// 输入数组的每个元素
for(int i=0;i<n;i++) { a[i]=scn.nextInt(); } System.out.println(muliptyMax(a)); } }

 

 
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部