628. 三个数的最大乘积 ——【Leetcode每日一题】

た入场券 2024-03-24 13:57 55阅读 0赞

### 628. 三个数的最大乘积 ###

给你一个整型数组 `nums` ，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

##### 示例 1： #####

> 输入：nums = \[1,2,3\]  
> 输出：6

##### 示例 2： #####

> 输入：nums = \[1,2,3,4\]  
> 输出：24

##### 示例 3： #####

> 输入：nums = \[-1,-2,-3\]  
> 输出：-6

##### 提示： #####

*   3 < = n u m s . l e n g t h < = 1 0 4 3 <= nums.length <= 10^4 3<=nums.length<=104
 *   − 1000 < = n u m s \[ i \] < = 1000 -1000 <= nums\[i\] <= 1000 −1000<=nums\[i\]<=1000

#### 思路： ####

*  法一：**冒泡法**，找出三个最大值，两个最小值；
 *  法二：**调用函数sort()**，全部排序，取三个最大值，两个最小值；
 *  法三：**直接比较**，找出三个最大值，两个最小值；

#### 代码：(Java、C++) ####

法一：**调用函数sort()**  
**Java**

import java.util.Arrays;
    
    public class MaximumProduct {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		int[] nums = {
        -100,-98,-1,2,3,4};
    		System.out.println(maximumProduct(nums));
    	}
    	public static int maximumProduct(int[] nums) {
        
    		int n = nums.length;
    		if(n == 3) {
        
    			return nums[0] * nums[1] * nums[2];
    		}
    		Arrays.sort(nums);
    		int end = nums[n - 1] * nums[n - 2] * nums[n - 3];
    		int fir = nums[0] * nums[1] * nums[n - 1];
    		return end > fir ? end : fir;
        }
    }

**C++**

class MaximumProduct {
        
    public:
    	int maximumProduct(vector<int>& nums) {
        
    		int n = nums.size();
    		sort(nums.begin(),nums.end());
    		int end = nums[n - 1] * nums[n - 2] * nums[n - 3];
    		int fir = nums[0] * nums[1] * nums[n - 1];
    		return end > fir ? end : fir;
    	}
    };
    int main() {
        
    
    	vector<int> nums = {
         -100,-98,-1,2,3,4 };
    
    	MaximumProduct m;
    
    	cout << m.maximumProduct(nums) << endl;
    
    	system("pause");
    	return 0;
    }

法二：**冒泡法**  
**Java**

public static int maximumProduct(int[] nums) {
        
    	int n = nums.length;
    	for(int j = 0; j < 3; j++) {
        
    		for(int i = 1; i < n - j; i++) {
        
    			if(nums[i - 1] > nums[i]) {
        
    				int temp = nums[i - 1];
    				nums[i - 1] = nums[i];
    				nums[i] = temp;
    			}
    		}
    	}
    	
    	for(int j = 0; j < 2; j++) {
        
    		for(int i = n - 3; i > j && i > 0; i--) {
        
    			if(nums[i - 1] > nums[i]) {
        
    				int temp = nums[i - 1];
    				nums[i - 1] = nums[i];
    				nums[i] = temp;
    			}
    		}
    	}
    	
    	int end = nums[n - 1] * nums[n - 2] * nums[n - 3];
    	int fir = nums[0] * nums[1] * nums[n - 1];
    	return end > fir ? end : fir;
    }

**C++**

class MaximumProduct {
        
    public:
    	int maximumProduct(vector<int>& nums) {
        
    		int n = nums.size();
    		
    		for (int j = 0; j < 3; j++) {
        
    			for (int i = 1; i < n - j; i++) {
        
    				if (nums[i - 1] > nums[i]) {
        
    					int temp = nums[i - 1];
    					nums[i - 1] = nums[i];
    					nums[i] = temp;
    				}
    			}
    		}
    
    		for (int j = 0; j < 2; j++) {
        
    			for (int i = n - 3; i > j && i > 0; i--) {
        
    				if (nums[i - 1] > nums[i]) {
        
    					int temp = nums[i - 1];
    					nums[i - 1] = nums[i];
    					nums[i] = temp;
    				}
    			}
    		}
    		int end = nums[n - 1] * nums[n - 2] * nums[n - 3];
    		int fir = nums[0] * nums[1] * nums[n - 1];
    		return end > fir ? end : fir;
    	}
    };

法三：**直接比较**  
**Java**

public int maximumProduct(int[] nums) {
        
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE, min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        for (int n : nums) {
        
            if (n > max1) {
        
                max3 = max2;
                max2 = max1;
                max1 = n;
            } else if (n > max2) {
        
                max3 = max2;
                max2 = n;
            } else if (n > max3) {
        
                max3 = n;
            }
    
            if (n < min1) {
        
                min2 = min1;
                min1 = n;
            } else if (n < min2) {
        
                min2 = n;
            }
        }
        return Math.max(max1*max2*max3, max1*min1*min2);
    }

##### 运行结果： #####

![在这里插入图片描述][cb76e3bfe34941b89b552cf12b1e10c3.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( N ) O(N) O(N)，其中  N N N 为数组长度。我们仅需遍历数组一次。
 *  **空间复杂度**： O ( 1 ) O(1) O(1)。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[cb76e3bfe34941b89b552cf12b1e10c3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/01accba67b17418dbe56658b7cb28017.png
[Link 1]: https://leetcode.cn/problems/maximum-product-of-three-numbers/description/
[leetCode]: http://t.csdn.cn/kQLJO