成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode 628 Maximum Product of Three Numbers

CoreDump / 3543人閱讀

摘要：題目詳情輸入一個大小大于等于三的數(shù)組，給出其中任意三個數(shù)乘積中的最大乘積想法這道題最主要的是要考慮正負數(shù)的情況。如果全都是正數(shù)相乘比較大，就取三個最大值相乘即可。

題目詳情 
Given an integer array, find three numbers whose product is maximum and output the maximum product.
輸入一個大小大于等于三的數(shù)組，給出其中任意三個數(shù)乘積中的最大乘積


Example 1:
Input: [1,2,3]
Output: 6
Example 2:
Input: [1,2,3,4]
Output: 24
想法

這道題最主要的是要考慮正負數(shù)的情況。

如果全都是正數(shù)相乘比較大，就取三個最大值相乘即可。

如果負數(shù)的絕對值比較大，我們可以取絕對值最大的兩個負數(shù)參與相乘，最后比較一下兩種算法的乘積哪個大。

解法一 時間復雜度O(n)

這個解法寫起來麻煩一點，判斷條件比較多，但是時間復雜度為O(n)

    public int maximumProduct(int[] nums) {
        Integer max1 = Integer.MIN_VALUE;Integer max2 = max1;Integer max3 = max1;
        Integer min1 = Integer.MAX_VALUE;Integer min2 = min1;
        
        for(int num : nums){
            if(num > max1){
                max3 = max2;
                max2 = max1;
                max1 = num;
            }else if(num > max2){
                max3 = max2;
                max2 = num;
            }else if(num > max3){
                max3 = num;
            }
            
            if(num < min1){
                min2 = min1;
                min1 = num;
            }else if(num < min2){
                min2 = num;
            }
            
        }
        
        
        return Math.max(max1*max2*max3, max1*min1*min2);
    }
解法二 預排序

先對數(shù)組進行預排序的算法比較簡潔，但是時間復雜度為O(nlogn)

    public int maximumProduct(int[] nums) {
        
         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;
    }

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/68419.html

相關(guān)文章

  • [LeetCode] 628. Maximum Product of Three Numbers

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

    jindong 評論0 收藏0

  • leetcode 部分解答索引（持續(xù)更新～）

    摘要：前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當時也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當時也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的?？赡艽蠹铱粗卜浅２环奖?。所以在這里做個索引嘻嘻。 順序整理 1~50 1...

    leo108 評論0 收藏0

  • 前端 | 每天一個 LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。 這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

    張漢慶 評論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 評論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 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<