628. 三个数的最大乘积

淡淡的烟草味﹌ 2023-07-26 05:29 47阅读 0赞

1.  三个数的最大乘积

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

#### 示例 1: ####

输入: [1,2,3]
    输出: 6

#### 示例 2: ####

输入: [1,2,3,4]
    输出: 24

注意:

给定的整型数组长度范围是\[3,10^4\]，数组中所有的元素范围是\[-1000, 1000\]。  
输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。

--------------------

### 解 ###

方法一：**排序法**

（1）对数组进行`倒序排序`。

（2）三个数的最大成绩有以下几个可能：

*  全是正数，则取前三个。
 *  全是负数，则取前三个。
 *  有正数有负数，则比较 **前三个数的乘积** 和 **第一个数与最后两个数的乘积** 哪个大。

代码如下：

from typing import List
    def maximumProduct(nums: List[int]) -> int:
    
        for i in range(len(nums)-1):
            for j in range(i+1,len(nums)):
                if nums[i] < nums[j]:
                    nums[i],nums[j] = nums[j],nums[i]
    
        return max(nums[0] * nums[1] * nums[2],nums[0] * nums[-2] * nums[-1])
    
    
    list_demo = [3,1,-1,1,-1,-2,-6]
    
    result = maximumProduct(list_demo)
    print(result)

时间复杂度为O(n^2)  
  
  
方法二：**线性扫描**

在方法一中，我们实际上只要求出数组中**最大的三个数**以及**最小的两个数**，因此我们可以不用排序，用线性扫描直接得出这五个数。

# 方法二： 找出最大的三个数和最小的两位数
    class Solution:
        def maximumProduct(self, nums: List[int]) -> int:
    
            min1,min2 = 1000,1000
            max1,max2,max3 = -1000,-1000,-1000
    
            for x in nums:
                
                if x < min1:
                    min2 = min1
                    min1 = x
                elif x< min2:
                    min2 = x
                
                if x > max1:
                    max3 = max2
                    max2 = max1
                    max1 = x
                elif x > max2:
                    max3 = max2
                    max2 = x
                elif x > max3:
                    max3 = x
                
            return max(max1 * max2 * max3,max1 * min2 * min1)