628. 三个数的最大乘积


628. 三个数的最大乘积

class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]);
    }

// 作者:LeetCode-Solution
// 链接:https://leetcode-cn.com/problems/maximum-product-of-three-numbers/solution/san-ge-shu-de-zui-da-cheng-ji-by-leetcod-t9sb/
}

复杂度分析
时间复杂度:O(NlogN),其中 N 为数组长度。排序需要 O(NlogN) 的时间。
空间复杂度:O(logN),主要为排序的空间开销。

排序

首先将数组排序。
如果数组中全是非负数,则排序后最大的三个数相乘即为最大乘积;如果全是非正数,则最大的三个数相乘同样也为最大乘积。
如果数组中有正数有负数,则最大乘积既可能是三个最大正数的乘积,也可能是两个最小负数(即绝对值最大)与最大正数的乘积。
综上,我们在给数组排序后,分别求出三个最大正数的乘积,以及两个最小负数与最大正数的乘积,二者之间的最大值即为所求答案.

    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 x : nums) {
            if (x < min1) &#123;
                min2 = min1;
                min1 = x;
            &#125; else if (x < min2) &#123;
                min2 = x;
            &#125;

            if (x > max1) &#123;
                max3 = max2;
                max2 = max1;
                max1 = x;
            &#125; else if (x > max2) &#123;
                max3 = max2;
                max2 = x;
            &#125; else if (x > max3) &#123;
                max3 = x;
            &#125;
        &#125;

        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    &#125;

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/maximum-product-of-three-numbers/solution/san-ge-shu-de-zui-da-cheng-ji-by-leetcod-t9sb/

线性扫描

实际上只要求出数组中最大的三个数以及最小的两个数,因此我们可以不用排序,用线性扫描直接得出这五个数。

复杂度分析

  • 时间复杂度:O(N)O(N),其中 NN 为数组长度。我们仅需遍历数组一次。

  • 空间复杂度:O(1)O(1)。


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
剑指 Offer 39. 数组中出现次数超过一半的数字 剑指 Offer 39. 数组中出现次数超过一半的数字
剑指 Offer 39. 数组中出现次数超过一半的数字class Solution &#123; public int majorityElement(int[] nums) &#123; int x
2021-02-27 future
下一篇 
53. 最大子序和 53. 最大子序和
53. 最大子序和难度简单 2926给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例 1:输入:nums = [-2,1,-3,4,-1,2,1,-5,4]输出:6解释:连续子数组
2021-02-27 future
  目录