Maximum Product of Three Numbers

题目介绍

LeetCode 628. Maximum Product of Three Numbers，题目的意思是在一个给定范围的整数数组里面寻找三个数积最大值。

解题思路

思路上面很清晰，三个最大数或者两个最小数和最大数，比较这两个值中较大的一个，则为最大值。

第一种（没通过）

先使用系统的排序函数排序，时间复杂度上没通过。

class Solution {
    func maximumProduct(_ nums: [Int]) -> Int {
        let sortNums = nums.sorted()
        return max(sortNums[0] * sortNums[1] * sortNums[nums.count - 1], sortNums[nums.count - 3] * sortNums[nums.count - 2] * sortNums[nums.count - 1])
    }
}

Complexity Analysis

• Time complexity : O(nlog(n)). Sorting the numsnums array takes nlog(n) time.
• Space complexity : O(log(n)). Sorting takes O(logn) space.

第二种

遍历数组，记录上述所需要的 5 个值，然后进行比较。时间复杂度为数组长度 O(n)。

class Solution {
    func maximumProduct(_ nums: [Int]) -> Int {
        var min1 = Int.max
        var min2 = Int.max
        var max1 = Int.min
        var max2 = Int.min
        var max3 = Int.min

        for num in nums {

            if num <= min1 {
                min2 = min1
                min1 = num
            } else if num <= min2 {
                min2 = num
            }

            if num >= max1 {
                max3 = max2
                max2 = max1
                max1 = num
            } else if num >= max2 {
                max3 = max2
                max2 = num
            } else if num >= max3 {
                max3 = num
            }
        }

        return max(min1 * min2 * max1, max1 * max2 * max3)
    }
}

Complexity Analysis

• Time complexity : O(n). Only one iteration over the numsnums array of length nn is required.
• Space complexity : O(1). Constant extra space is used.

**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文首发于Ivan’s Blog | 叶帆的博客博客（ http://yeziahehe.com ），版权所有，侵权必究。

本文链接：http://yeziahehe.com/2017/11/03/MaximumProductOfThreeNumbers/