文档章节

获取三个数的最大乘积 Maximum Product of Three Numbers

叶枫啦啦
 叶枫啦啦
发布于 2017/06/26 17:45
字数 273
阅读 14
收藏 0

问题:

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3]
Output: 6

Example 2:

Input: [1,2,3,4]
Output: 24

Note:

  1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
  2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

解决:

要考虑到值为负数的情况

public class Solution {
    public int maximumProduct(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int a = nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3];
        int b = nums[0] * nums[1] * nums[nums.length - 1];

        return a > b ? a : b;
    }
}

② 线性遍历数组,依次找到最大的三个值和最小的两个值,因为三个负数相乘为负数。

public class Solution {
    public int maximumProduct(int[] nums) {
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        for (int n: nums) {
            if (n <= min1) {
                min2 = min1;
                min1 = n;
            } else if (n <= min2) {
                min2 = n;
            }
            if (n >= max1) {
                max3 = max2;
                max2 = max1;
                max1 = n;
            } else if (n >= max2) {
                max3 = max2;
                max2 = n;
            } else if (n >= max3) {
                max3 = n;
            }
        }
        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 12
博文 569
码字总数 354997
作品 0
海淀
私信 提问
628. Maximum Product of Three Numbers。

Given an integer array, find three numbers whose product is maximum and output the maximum product. Example 1: Input: [1,2,3] Output: 6 Example 2: Input: [1,2,3,4] Output: 24 给......

Leafage_M
01/08
0
0
PAT A1037. Magic Coupon (25)

https://www.patest.cn/contests/pat-a-practise/1037 The magic shop in Mars is offering some magic coupons. Each coupon has an integer N printed on it, meaning that when you use t......

阿豪boy
2017/02/26
0
0
欧拉计划的Python解法(1-10)

Problem 1. Multiples of 3 and 5 If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of......

prpr
2014/03/13
0
3
Codeforces Round #456 Div.2 B. New Year's Eve

Problem codeforces.com/contest/912/problem/B Analysis You can choose k or less than k integers from 1~n, calculate maximum xor result (1) k = 1, You can only choose one integer,......

翡翠森林Z
01/09
0
0
LeetCode 152. Maximum Product Subarray (最大乘积子数组)

Given an integer array , find the contiguous subarray within an array (containing at least one number) which has the largest product. Example 1: Example 2: Reference Answer 思路......

dby_freedom
前天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

python机器学习及实践学习笔记1-如何打开ipynb后缀文件

python机器学习及实践学习笔记1-如何打开ipynb后缀文件 2017年02月22日 14:58:08 hustzhoutian 阅读数:45365更多 个人分类: 深度学习 需要安装ipython notebook,如果你已经安装Anaconda软...

linjin200
3分钟前
0
0
关于在vim中的查找和替换

1,查找 在normal模式下按下/即可进入查找模式,输入要查找的字符串并按下回车。 Vim会跳转到第一个匹配。按下n查找下一个,按下N查找上一个。 Vim查找支持正则表达式,例如/vim$匹配行尾的"...

休辞醉倒
7分钟前
0
0
in_array的坑

PHP in_array的坑 ps: 应该是弱类型语言的坑 php文档 顾名思义,in_array就是查找一个值是否在数组里面。 问题 事故现场 一个sql注入的测试代码如下: $type = $_GET['type'];$types = [2,3,...

o0无忧亦无怖
7分钟前
11
1
Yarn(包管理器) 的基本用法

Yarn是一个快速、可靠、安全的依赖管理工具,是npm的代替品。 Yarn对你的代码来说是一个包管理工具,你可以通过它使用全世界开发者的代码,或者分享自己的代码。 安装Yarn: 操作系统不同,安...

帝子兮
9分钟前
0
0
阿里云HBase全新发布X-Pack NoSQL数据库再上新台阶

一、八年双十一,造就国内最大最专业HBase技术团队 阿里巴巴集团早在2010开始研究并把HBase投入生产环境使用,从最初的淘宝历史交易记录,到蚂蚁安全风控数据存储。持续8年的投入,历经8年双...

阿里云官方博客
9分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部