GuoXin Li's Blog

LeetCode628. Maximum Product of Three Numbers

LeetCode
字数统计: 315阅读时长: 1 min
2020/03/07 Share

628. Maximum Product of Three Numbers

628. Maximum Product of Three Numbers

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3]
Output: 6

Example 2:

Input: [1,2,3,4]
Output: 24

Note:

The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

Solution one

1
2
3
4
5
6
7
//java
class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        return Math.max(nums[0] * nums[1] * nums[nums.length-1], nums[nums.length-1]* nums[nums.length-2] * nums[nums.length-3]);
    }
}

Solution 1

Most important key of solution is that the negative situation may be contained in array.

return two miximum * one maximum compared to three maximum.

Time complexity: O(nlogn)

Space complexity: O(0)

1
2
3
4
5
6
7
8
9
//c++
class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        return max(nums[0] * nums[1] * nums[n-1], nums[n-1] * nums[n - 2] * nums[n - 3]);
    }
};
  • sort( begin( ), end( ) );
  • sort( rbegin( ), rend( ) );

solution 2

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
//java
class Solution {
    public int maximumProduct(int[] nums) {
        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_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;
            }
        }
        return Math.max( max1 * min1 * min2, max1 * max2 * max3 );
    }
}

note: In C++, max is INT_MAX, min is INT_MIN

CATALOG
  1. 1. 628. Maximum Product of Three Numbers
  2. 2. Example 2:
  3. 3. Note:
  4. 4. Solution one
  5. 5. solution 2
Total : 89
2022
2021
2020
2019
2018
essay Deep Learning Paper-reading learning-note C++ CUDA cmake LeetCode DataStructure Numpy OS-Linux PAT slidingwindow git golang BuaaAssignments CG
Machine-Learning Data-Structure