文档章节

Maximum Product of Three Numbers

叶枫啦啦
 叶枫啦啦
发布于 2017/06/26 17:45
字数 230
阅读 12
收藏 0
点赞 0
评论 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);
    }
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 3
博文 540
码字总数 260604
作品 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

PAT (Advanced Level) 1007. Maximum Subsequence Sum (25) dp

题目链接 1007. Maximum Subsequence Sum (25) Time limit:400 ms Memory limit:65536 kB Problem Descrpition Given a sequence of K integers { N1, N2, …, NK }. A continuous subseque......

xp731574722 ⋅ 03/13 ⋅ 0

C♯ 7 中的 Tuple 特性

原文出处:SANDEEP SINGH 译文出处:oschina 介绍 Tuple是异类对象的有序序列。 我们经常可以写出返回多个值的方法,所以我们需要创建一个包含多个数据元素的简单结构。 为了支持这些情况,T...

SANDEEP SINGH ⋅ 2017/03/29 ⋅ 0

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

140个Google的面试题

陈皓 发表于 2010年12月02日 08:44 | Hits: 310 来源:http://blog.seattleinterviewcoach.com/2009/02/140-google-interview-questions.html(墙) 某猎头收集了140多个Google的面试题,都张......

风林火山 ⋅ 2010/12/19 ⋅ 0

140个Google面试问题

原文地址:http://www.cnblogs.com/hanyulcf/archive/2010/12/03/1895934.html 某猎头收集了140多个Google的面试题,都张到他的Blog中了,主要是下面这些职位的,因为被墙,且无任何敏感信息...

迷途d书童 ⋅ 2012/03/30 ⋅ 0

Cisco Unified CME 7.1 Supported Firmware, Platforms, Memory, and Voice Products

Revised: December 22, 2012 转载于http://www.cisco.com/c/en/us/td/docs/voiceipcomm/cucme/requirements/guide/cme71spc.html...

kidling ⋅ 2015/10/22 ⋅ 0

决战Leetcode: easy part(51-96)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999 ⋅ 02/09 ⋅ 0

UVa 100-The 3n + 1 problem

【问题描述】 Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzi......

落叶-归根 ⋅ 2016/05/03 ⋅ 0

codeforces 262B Roma and Changing Signs

Roma works in a company that sells TVs. Now he has to prepare a report for the last year. Roma has got a list of the company's incomes. The list is a sequence that consists of n......

yongzhong ⋅ 2015/04/02 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JVM堆的理解

在JVM中,我们经常提到的就是堆了,堆确实很重要,其实,除了堆之外,还有几个重要的模块,看下图: 大 多数情况下,我们并不需要关心JVM的底层,但是如果了解它的话,对于我们系统调优是非常...

不羁之后 ⋅ 昨天 ⋅ 0

推荐:并发情况下:Java HashMap 形成死循环的原因

在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障,并且这个事发生了很多次,原因是在Java语言在并发情况下使用HashMap造成Race Condition,从而导致死循环。这个事情我4、5年前也经历...

码代码的小司机 ⋅ 昨天 ⋅ 1

聊聊spring cloud gateway的RetryGatewayFilter

序 本文主要研究一下spring cloud gateway的RetryGatewayFilter GatewayAutoConfiguration spring-cloud-gateway-core-2.0.0.RC2-sources.jar!/org/springframework/cloud/gateway/config/G......

go4it ⋅ 昨天 ⋅ 0

创建新用户和授予MySQL中的权限教程

导读 MySQL是一个开源数据库管理软件,可帮助用户存储,组织和以后检索数据。 它有多种选项来授予特定用户在表和数据库中的细微的权限 - 本教程将简要介绍一些选项。 如何创建新用户 在MySQL...

问题终结者 ⋅ 昨天 ⋅ 0

android -------- 颜色的半透明效果配置

最近有朋友问我 Android 背景颜色的半透明效果配置,我网上看资料,总结了一下, 开发中也是常常遇到的,所以来写篇博客 常用的颜色值格式有: RGB ARGB RRGGBB AARRGGBB 这4种 透明度 透明度...

切切歆语 ⋅ 昨天 ⋅ 0

CentOS开机启动subversion

建立自启动脚本: vim /etc/init.d/subversion 输入如下内容: #!/bin/bash## subversion startup script for the server## chkconfig: 2345 90 10# description: start the subve......

随风而飘 ⋅ 昨天 ⋅ 0

Nginx + uwsgi @ubuntu

uwsgi 安装 sudo apt-get install python3-pip # 注意 ubuntu python3默认没有安装pippython3 -m pip install uwsgi 代码(test.py) def application(env, start_response): start_res......

袁祾 ⋅ 昨天 ⋅ 0

版本控制工具

CSV , SVN , GIT ,VSS

颖伙虫 ⋅ 昨天 ⋅ 0

【2018.06.19学习笔记】【linux高级知识 13.1-13.3】

13.1 设置更改root密码 13.2 连接mysql 13.3 mysql常用命令

lgsxp ⋅ 昨天 ⋅ 0

LVM

LVM: 硬盘划分分区成物理卷->物理卷组成卷组->卷组划分逻辑分区。 1.磁盘分区: fdisk /dev/sdb 划分几个主分区 输入t更改每个分区类型为8e(LVM) 使用partprobe生成分区的文件:如/dev/sd...

ZHENG-JY ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部