寻找三个数的最高乘积 [英] Finding highest product of three numbers

问题描述

给出一个整数数组， arrayofints ，找到最高的产品，最高产品，您可以从三个整数。输入的整数数组将始终至少包含三个整数。

Given an array of ints, arrayofints, find the highest product, Highestproduct, you can get from three of the integers. The input array of ints will always have at least three integers.

因此，我从 arrayofints 中弹出了三个数字并将其卡在最高产品：

So I've popped three numbers from arrayofints and stuck them in highestproduct:

Highestproduct = arrayofints[:2]
for item in arrayofints[3:]:
    If min(Highestproduct) < item:
        Highestproduct[highestproduct.index(min(Highestproduct))] = item

如果少于最高产品的最小：用当前编号替换最低的编号。

If min of highestproduct less than item: Replace the lowest number with the current number.

最终将获得最高的产品，但是显然有更好的解决方案。我的方法有什么问题？我的解决方案是O（n）吗？

This would end up with highest product, but apparently there is a better solution. What's wrong with my approach? Would my solution be O(n)?

推荐答案

跟踪两个最小元素和三个最大元素，答案应该是 min1 * min2 * max1 或 max1 * max2 * max3 。

Keep track of the two minimal elements and three maximal elements, the answer should be min1 * min2 * max1 or max1 * max2 * max3.

要获得3个整数的最大乘积，我们必须选择3个最大元素。但是有一个问题，我们可以用2 min整数替换3个max元素中最小的2个元素。如果两个最小整数均为负，则其乘积为正，因此 min1 * min2 可能大于 max2 * max3 （其中 max2 和 max3 是数组中3个max元素中最小的2个。

To get the maximum product of 3 ints we have to choose 3 maximum elements. However there is a catch that we can substitute 2 of the smallest of 3 max elements with the 2 min ints. If both smallest ints are negative their product is positive so min1 * min2 might be bigger than max2 * max3 (where max2 and max3 are 2 of the smallest of 3 max elements from the array).

这可以在 O（n）时间内运行。

这篇关于寻找三个数的最高乘积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！