[LeetCode] 628. Maximum Product of Three Numbers

jindong 发布于2019-08-16 13:39 / 3367人阅读

Problem

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:
The length of the given array will be in range [3,10^4] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won"t exceed the range of 32-bit signed integer.

Solution follow-up: max product of k numbers

class Solution {
    public int maximumProduct(int[] nums) {
        int len = nums.length;
        if (len < 3) return 0;
        Arrays.sort(nums);
        if (nums[0]*nums[len-1] >= 0) {
            return nums[len-1]*nums[len-2]*nums[len-3];
        }
        int l = 0, r = len-1, res = 1, count = 3;
        while (count > 0) {
            if (count%2 == 1) {
                res *= nums[r];
                r -= 1;
                count -= 1;
            }
            else {
                if (nums[r]*nums[r-1] > nums[l]*nums[l+1]) {
                    res *= nums[r]*nums[r-1];
                    r -= 2;
                } else {
                    res *= nums[l]*nums[l+1];
                    l += 2;
                }
                count -= 2;
            }
        }
        return res;
    }
}

云服务器 GPU云服务器 Numbers Maximum LeetCode Product

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72091.html

leetcode 628 Maximum Product of Three Numbers

摘要：题目详情输入一个大小大于等于三的数组，给出其中任意三个数乘积中的最大乘积想法这道题最主要的是要考虑正负数的情况。如果全都是正数相乘比较大，就取三个最大值相乘即可。题目详情 Given an integer array, find three numbers whose product is maximum and output the maximum product.输入一个大小大于...

CoreDump 2019-08-15 13:57 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
[LeetCode/LintCode] Largest Palindrome Product

Problem Find the largest palindrome made from the product of two n-digit numbers. Since the result could be very large, you should return the largest palindrome mod 1337. Example Input: 2Output: 987Ex...

Barry_Ng 2019-08-15 18:16 评论0 收藏0
[LeetCode] 575. Distribute Candies

Problem Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribu...

djfml 2019-08-16 13:47 评论0 收藏0