三个数的最大乘积

zyfsuzy 的个人博客 / 0 / 2 / 创建于 5年前 / 更新于 5年前

题目

给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

示例 1:

输入: [1,2,3]
输出: 6
示例 2:

输入: [1,2,3,4]
输出: 24

解题思路

1. 分为三种情况，全部正数，全部负数，有正数，有负数

2. 全部正数/负数取排序后三最大三位

3. 有正有负，最大乘积出现在两端

代码

```java

class Solution {

public int maximumProduct(int[] nums) {

    if(nums == null || nums.length < 3)

        return 0;

    Arrays.sort(nums);

    //全部正数

    if(nums[0] >= 0 ){

        return nums[nums.length-1] * nums[nums.length-2] *nums[nums.length-3];

    }

    //全部负数

    if(nums[nums.length-1] <= 0){

        return nums[nums.length-1] * nums[nums.length-2] *nums[nums.length-3];

    }

    //有正数有负数

    return   Math.max(nums[0]*nums[1]*nums[nums.length-1], nums[nums.length-1] * nums[nums.length-2] *nums[nums.length-3]);

}

}

本作品采用《CC 协议》，转载必须注明作者和本文链接

讨论数量: 2

swing07

0 声望

从算法的角度来说排序不合适吧应该一次循环找出三个数据直接乘

5年前评论

zyfsuzy

27 声望

@swing07 你写一下试试，怎么找到三个数，可以贴一下你的代码不

public int maximumProduct(int[] nums) { if(nums == null || nums.length < 3) return 0; int negative,positive; int maxPositiveTree[3] = {0}; // 最大的三个正数 int maxAbsNegativeTree[3] = {0}; // 绝对值最大三个负数 int maxNegativeTree[3] = {0}; // 最大的三个负数 for (i=0;i<nums.length;i++ ) { if (nums[i]<0) { negative++; // if(nums[i]<maxNegativeTree[2]){ maxNegativeTree[2] = nums[i]; } else if (nums[i]<maxNegativeTree[1]) { maxNegativeTree[1] = nums[i]; } else if (nums[i]<maxNegativeTree[0]) { maxNegativeTree[0] = nums[i]; } // if(abs(nums[i])>abs(maxAbsNegativeTree[2])){ maxAbsNegativeTree[2] = nums[i]; } else if (abs(nums[i])>abs(maxAbsNegativeTree[1]) { maxAbsNegativeTree[1] = nums[i]; } else if (abs(nums[i])>abs(maxAbsNegativeTree[0]) { maxAbsNegativeTree[0] = nums[i]; } } else { positive++; if(nums[i]>maxPositiveTree[2]){ maxPositiveTree[2] = nums[i]; } else if (nums[i]>maxPositiveTree[1]) { maxPositiveTree[1] = nums[i]; } else if (nums[i]>maxPositiveTree[0]) { maxPositiveTree[0] = nums[i]; } } } // 都是整数 if (negative<1){ return maxPositiveTree[0]maxPositiveTree[1]maxPositiveTree[2]; } // 都是负数 if (negative<1){ return maxNegativeTree[0]maxNegativeTree[1]maxNegativeTree[2]; } return Math.max(maxPositiveTree[0]maxPositiveTree[1]maxPositiveTree[2],maxPositiveTree[0]maxPositiveTree[1]maxAbsNegativeTree[0]); }

简单写了一下思路大概是代码那个你看看我没验证。

zyfsuzy （作者）（楼主）

@swing07 时间复杂度多少，我写的是 logn

@swing07 你这代码看的人脑壳疼，我写的思路跟官方题解一样的思路

@swing07 能用 markdown 语法不

@zyfsuzy public int maximumProduct(int[] nums) { if(nums == null || nums.length < 3) return 0; int negative,positive; int maxPositiveTree[3] = {0}; // 最大的三个正数 int maxAbsNegativeTree[3] = {0}; // 绝对值最大三个负数 int maxNegativeTree[3] = {0}; // 最大的三个负数 for (i=0;i<nums.length;i++ ) { if (nums[i]<0) { negative++; // if(nums[i]<maxNegativeTree[2]){ maxNegativeTree[2] = nums[i]; } else if (nums[i]<maxNegativeTree[1]) { maxNegativeTree[1] = nums[i]; } else if (nums[i]<maxNegativeTree[0]) { maxNegativeTree[0] = nums[i]; } // if(abs(nums[i])>abs(maxAbsNegativeTree[2])){ maxAbsNegativeTree[2] = nums[i]; } else if (abs(nums[i])>abs(maxAbsNegativeTree[1]) { maxAbsNegativeTree[1] = nums[i]; } else if (abs(nums[i])>abs(maxAbsNegativeTree[0]) { maxAbsNegativeTree[0] = nums[i]; } } else { positive++; if(nums[i]>maxPositiveTree[2]){ maxPositiveTree[2] = nums[i]; } else if (nums[i]>maxPositiveTree[1]) { maxPositiveTree[1] = nums[i]; } else if (nums[i]>maxPositiveTree[0]) { maxPositiveTree[0] = nums[i]; } } } // 都是整数 if (negative<1){ return maxPositiveTree[0]*maxPositiveTree[1]*maxPositiveTree[2]; } // 都是负数 if (negative<1){ return maxNegativeTree[0]*maxNegativeTree[1]*maxNegativeTree[2]; } return Math.max(maxPositiveTree[0]*maxPositiveTree[1]*maxPositiveTree[2],maxPositiveTree[0]*maxPositiveTree[1]*maxAbsNegativeTree[0],maxPositiveTree[0]*maxAbsNegativeTree[0]*maxAbsNegativeTree[1]); }

@zyfsuzy 你可以自己贴出去格式话下

@swing07 我都不用试，你的绝对过不了测试用例

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助

三个数的最大乘积

题目

解题思路

代码

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

三个数的最大乘积

题目

解题思路

代码

社区赞助商

关于 LearnKu

资源推荐

服务提供商

其他信息

请登录