阵列中3个数字的最大乘积

本文介绍了阵列中3个数字的最大乘积的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我在最近的一次采访中遇到了这个问题。 给定一个数组，找到可以获得的最大乘积乘以数组中的任何3个数字。 我想出的解决方案是，

I came across this question in a recent interview. Given an array find the maximum product that can be obtained multiplying any 3 numbers in the array. The solution I came up with is,

Sort the array Multiply the 3 largest number.

这是 O（nlogn）

是否有 O（n）问题的解决方案？

Is there a O(n) solution to the problem?

推荐答案

您可以保留前三个，而不是排序所有值，即 O（3n），这是 O（n）

Instead of sorting all the values, you can retain the top three, which is O(3n) which is O(n)

在一次通过中执行此操作可能比三次通过更有效。

Doing this in a single pass is likely to be more efficient than three passes.

这样做的一种方法是对3的数组进行插入排序，每次丢弃最低值。 （你可以从数组中的最低值开始）

One way of doing this is to do an insertion sort into an array of 3, discarding the lowest value each time. (you can start at the lowest value in the array)

你也可以使用一系列if / else比较来实现这个来更新3个变量。

You can also implement this using a series of if/else comparison to update 3 variables.

负片怎么样？

How about negatives?

唯一的复杂因素是如果你可以有负值，例如 5 * -4 * -4> 5 * 5 * 3

The only complication is if you can have negative values e.g. 5 * -4 * -4 > 5 * 5 * 3

因此，搜索三个最大和两个最负面的信息是有意义的。您可以检查最大*下两个最大的或最大*两个最负面的是。

For this reason it would makes sense to search for the three largest and the two most negative. You can check whether the largest * the next two largest or largest * the two most negative is bigger.

如果它们全部为负数怎么办？

what if they are all negative?

在这种情况下，您还需要三个最小的负值，以使产品最接近正无穷大。

In this case, you also need the three smallest negative values as well to get the product closest to positive infinity.