首页 > itarticle > algorithm notes: leetcode#628 maximum product of three numbers

algorithm notes: leetcode#628 maximum product of three numbers

admin 11月 12, 2020 0

Problem

Solution 1

Analysis

Python implementation

1
2
3
4
5
6
7
8
 
class (object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return nums[-1]*max(nums[0]*nums[1], nums[-2]*nums[-3])

Java implementation

1
2
3
4
5
6
7
8
 
class  {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int sum1 = nums[0]*nums[1];
        int sum2 = nums[nums.length-2]*nums[nums.length-3];
        return nums[nums.length-1]*(sum1 > sum2 ? sum1 : sum2);
    }
}

Time complexity

O(nlogn).

Space complexity

O(nlogn).

Solution 2

Analysis

Python implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
class (object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        min1, min2, max1, max2, max3 = float('Inf'), float('Inf'), float('-Inf'), float('-Inf'), float('-Inf')
        for num in nums:
            if num > max1:
                max1, max2, max3 = num, max1, max2
            elif num > max2:
                max2, max3 = num, max2
            elif num > max3:
                max3 = num
            if num < min1:
                min1, min2 = num, min1
            elif num < min2:
                min2 = num
        return max1*max(max2*max3, min1*min2)

Java implementation

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
 
class  {
    public int maximumProduct(int[] nums) {
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;
        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;
            }
        }
        int sum1 = max2*max3;
        int sum2 = min1*min2;
        return (sum1 > sum2 ? sum1 : sum2)*max1;
    }
}

Time complexity

O(n).

Space complexity

O(1).

628. Maximum Product of Three Numbers
(中文版) 算法笔记: 力扣#628 三个数的最大乘积

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能