leetcode628-- Maximum Product of Three Numbers

leetcode628-- 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

题目很容易懂,即在一个数组中找到积最大的三个数,并将结果返回,如果数组中的数都是正的话,比较容易,

直接排个序,返回最后三个数的积就可以了,但是如果有负数和0呢?

也可以类似的分析,假设数组已经排好序了,

  • case2 全是负数

这时候因为三个数的积仍是负数,从而绝对值越小积越大,从而还是右边的三个数的积最大

  • case3 负数不少于两个

这时候最小的两个负数的积可能是个很大的正数,然后再和最大的正数相cheng.

最终可以这样写

class Solution(object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
    
        # 特别情况
        if len(nums) == 3:
            return nums[0]*nums[1]*nums[2]
        
        nums.sort()
        return max(nums[0]*nums[1]*nums[-1], nums[-1]*nums[-2]*nums[-3])
        

还有一种方法,即上面的代码中如果没有排序的话,就是只用到了5个数而已,即最大的三个数,和最小的两个数,那直接把这5个数求出来的话也是可以的,这个想法来自于之前做的第414题求第三大的数,不过那里是求的不记重数的,即两个2的话只算一个,这里并不是这样的,这里相当于是记重数的,因此没有加相等的时候直接pass的情况

class Solution(object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
    
        if len(nums) ==3:
            return nums[0]*nums[1]*nums[2]
        
        mx1 = float("-inf")
        mx2 = float("-inf")
        mx3 = float("-inf")
        
        mi1 = float("inf")
        mi2 = float("inf")
        
        for x in nums:
           
            if x> mx1:
                mx3 =mx2
                mx2 = mx1
                mx1 = x
            elif x>mx2:
                mx3 = mx2
                mx2 = x
            elif x>mx3:
                mx3 = x
            
            if x< mi1:
                mi2 = mi1
                mi1 =x 
            elif x< mi2:
                mi2 = x
                
  
        return max(mi1*mi2*mx1, mx1*mx2*mx3)

上面的写的太长了,可以简化成

class Solution(object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
    
        if len(nums) ==3:
            return nums[0]*nums[1]*nums[2]
        
        mx1 = float("-inf")
        mx2 = float("-inf")
        mx3 = float("-inf")
        
        mi1 = float("inf")
        mi2 = float("inf")
        
        for x in nums:
           
            if x> mx1:
                mx1, mx2, mx3 = x, mx1, mx2
            elif x>mx2:
                mx2, mx3 = x, mx2
            elif x>mx3:
                mx3 = x
            if x< mi1:
                mi1, mi2 = x, mi1
            elif x< mi2:
                mi2 = x
                
  
        return max(mi1*mi2*mx1, mx1*mx2*mx3)

如果用上面排序的话,就是O(nlogn)了,而用下面的那5个数的时候,就是O(n) 了.所以下面的方式虽然写起来不是那么地漂亮, 但是时间效率确实是高一些.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦