python - 数组中3个整数的最大乘积

Question

我正在尝试解决一个问题，我想找到数组中任意 3 个整数的最大乘积。

我尝试了我的解决方案:

def maximumProduct(nums):
    """
    :type nums: List[int]
    :rtype: int
    """

    list_of_ints = nums

    t = sorted(list_of_ints[:4])

    max_pos = t[2] 
    max_pos_2 = t[1]
    max_pos_3 = t[0]

    min_neg = 0
    min_neg_2 = 0

    for x in list_of_ints[3:]:
        if x<0 and x< min_neg:
            temp = min_neg
            min_neg = x
            min_neg_2 = temp

        elif x<0 and x<min_neg_2: 
            min_neg_2 = x

        if x>0 and x>max_pos:
            temp = max_pos
            max_pos = x
            temp2 = max_pos_2
            max_pos_2 = temp
            max_pos_3 = temp2

        elif x>0 and x>max_pos_2:
            temp = max_pos_2
            max_pos_2 = x
            max_pos_3 = temp

        elif x>0 and x>max_pos_3:
            max_pos_3 = x

    return max(max_pos*max_pos_2*max_pos_3, min_neg*min_neg_2*max_pos)

上述解决方案在输入 nums = [-1, -2, -3] 时失败。预期输出为-6，程序输出为0。

这是由于 min_neg 和 min_neg_1 初始化为零所致。

如何初始化以避免这个问题？我总是无法设置正确的初始化。

Answer 1

方法

要有效地解决此类问题，您需要认识到只有几种可能的情况。关注数字的符号并思考结果的符号是什么:

+ * + * + = +  (good)
+ * + * - = -  (bad)
+ * - * - = +  (good)
- * - * - = -  (bad)
anything * 0 = 0 (neutral)

因此，如果列表既有负数也有负数，则答案要么是三个最大数的乘积，要么是两个最小(负)数与最大数(正数)的乘积。

如果此条件不成立，则答案必须是数组中最大数字的乘积。

O(n log (n)) 解

所以，答案必须是排序后数组中的最后三个元素，或者两个第一个和最后一个，然后将它们相乘。最简单和最优雅的方法是首先对数字列表进行排序:

def maximum_product(nums): # O(n log(n)) solution
   nums.sort()
   assert len(nums) >= 3 # assume the input has been validated
   a1 = nums[-1] * nums[-2] * nums[-3]
   a2 = nums[0] * nums[1] * nums[-1]
   return max(a1, a2)

O(n) 解

但是，您也可以在 O(n) 时间内找到最大的三个数和最小的两个数。如何在容器中找到最大 N 数字的一种有效方法是在迭代时保持大小为 N 的堆。最后，堆包含答案:N 个最大元素的部分排序列表。

Python 模块 heapq 提供 convenient API为此:函数 nlargest() 和 nsmallest()。所以我们开始吧:

import heapq

def maximum_product(nums): # O(n) solution
   assert len(nums) >= 3 # assume the input has been validated
   max3 = heapq.nlargest(3, nums)
   min2 = heapq.nsmallest(2, nums)
   a1 = max3[0] * max3[1] * max3[2]
   a2 = min2[0] * min2[1] * max(max3)
   return max(a1, a2)