Fork me on GitHub

Maximum Product of Three Numbers

题目介绍

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

解题思路

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

第一种(没通过)

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

1
2
3
4
5
6
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)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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/