[LeetCode] 628. Maximum Product of Three Numbers

jindong 發布于2019-08-16 13:39 / 3468人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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