找到乘法最大的数字会导致一个O(n)通过一个数组

Question

问题：给定一个数组，您需要在数组中找到3个元素，这些元素在相乘时将给出所有元素的最大乘积。

例如，给定以下输入：

-4, 1, -8, 9, 6

预期输出是-4、-8、9，作为-4 * -8 * 9 == 288。

您可以假设数组中没有null。签名必须是public static int findTriplet(int[] a);。

我的代码：

public static int findTriplet(int[] a) {
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE,
maxLowby2 = Integer.MIN_VALUE, maxLowby1 = Integer.MIN_VALUE,
secondMin = Integer.MAX_VALUE, minIndex = -1, maxIndex = -1, indexofLowby1 = -1;

//we run a for loop to go over the array and collect all our needed information.
for (int i = 0; i < a.length; i++) {
//first we find the smallest value
if (min > a[i] && a[i] < 0) {
min = a[i];
minIndex = i;// we save the index so we can find other num that is negative and is different from this 1
////here we try to find the second smallest num in the array in such that it has to be a minus otherwise we wont be able to get a popsitive number(-1*-1=positive)
//if the index is different and second Min is smaller then the value in a[i] and a[i] must be a negetive num;
} else if (minIndex != i && secondMin > a[i] && a[i] < 0) {
secondMin = a[i];
}
//
if (max < a[i]) {
max = a[i];
maxIndex = i;
//now we look for only positive numbers
//here we need to find two other sumbers that are the biggest in the array but are different then each other.
} else if (max > a[i] && a[i] >= 0 && maxLowby1 < a[i] && maxIndex != i) {
maxLowby1 = a[i];
indexofLowby1 = i;
//here we find the last positive number that will be smaller the max and maxlowBy1
} else if (a[i] >= 0 && indexofLowby1 != i)
maxLowby2 = a[i];
}
// we creat the needed numbers and return the max value of them.
int finalMax = max * maxLowby2 * maxLowby1;
int secondMinus = max * min * secondMin;
return Math.max(finalMax, secondMinus);
} ```

Answer 1

您可以使用：

import java.util.Arrays;
public class LargestMultiple {
private static void storeValues(
int new_value,
int[] values
)
{
int i = -1;
for (;i + 1 < values.length && new_value > values[i+1]; ++i){}
if (i >= 0)
{
for (int j = 0; j < i; ++j)
{
values[j] = values[j+1];
}
values[i] = new_value;
}
}
public static int findTriplet(
int[] a
)
{
if (a.length == 0)
{
throw new IllegalArgumentException("Not enough values");
}
if (a.length <= 3)
{
int value = a[0];
for (int i = 1; i < a.length; ++i)
{
value *= a[i];
}
return value;
}
int[] maximums = {0, 0, 0};
int[] minimums = {0, 0};
int[] negatives = {Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE};
int num_positive = 0;

for (int i = 0; i < a.length; i++)
{
if (a[i] < 0)
{
storeValues(-a[i], minimums);
storeValues(a[i], negatives);
}
else
{
storeValues(a[i], maximums);
num_positive++;
}
}
if (num_positive > 0)
{
return Math.max(
minimums[0] * minimums[1],
maximums[0] * maximums[1]
) * maximums[2];
}
else
{
return negatives[0] * negatives[1] * negatives[2];
}
}

public static void test(final int[] values)
{
System.out.println(
Arrays.toString(values)
+ " -> "
+ findTriplet(values)
);
}
public static void main(final String[] args)
{
test(new int[]{1});
test(new int[]{1, 2});
test(new int[]{1, 2, 3});
test(new int[]{1, 2, 3, 4});
test(new int[]{1, 2, -1, -2});
test(new int[]{1, 2, -1});
test(new int[]{1, 2, 3, -1});
test(new int[]{1, 2, 3, -1, -4});
test(new int[]{-1, -2, -3, -4});
}
}

哪个输出：

[1] -> 1
[1, 2] -> 2
[1, 2, 3] -> 6
[1, 2, 3, 4] -> 24
[1, 2, -1, -2] -> 4
[1, 2, -1] -> -2
[1, 2, 3, -1] -> 6
[1, 2, 3, -1, -4] -> 12
[-1, -2, -3, -4] -> -6

注意：虽然storeValues在数组大小上是O(N(，但它总是从具有固定大小数组的findTriplet调用，然后，在该函数中，它将具有恒定的O(1(执行时间

Answer 2

结果始终是3个最高数字或最高数字与2个最低数字的乘积。因此，必须找到最低的2个和最高的3个数字。因此，O(n(解是可能的，因为这可以在一次循环中完成

public static int findTriplet(int[] a) {
if(a.length < 3) throw new IllegalArgumentException("The array must have a length of at least 3!");
int[] n = {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE };
for(int i : a) {
// find two lowest
if(i < n[0]) { n[1] = n[0]; n[0] = i; } 
else if (i < n[1]) n[1] = i;
// find three highest
if(i > n[4]) { n[2] = n[3]; n[3] = n[4]; n[4] = i; }
else if(i > n[3]) { n[2] = n[3]; n[3] = i; } 
else if(i > n[2]) n[2] = i;
}
int case1 = n[0] * n[1];
int case2 = n[2] * n[3];
return n[4] * (case1 > case2 ? case1 : case2);
}

Answer 3

如果只需要跟踪三个值，那么很容易避免内部循环。分别记录积极因素和消极因素。你只需要记录两个最小的负片。

将每个新数字与以前已知的值进行比较。通过下拉，您可以确定将值向下滑动(根据绝对值(并插入新值的位置。

对三个值的特殊情况作了明确的处理。所有三个初始值都是单独捕获的，并且仅在本例中使用。这确实假设列表中至少有三个值。

n1 = n2 = p1 = p2 = p3 = 0;  // negatives / positives with largest abs()
m3 = m2 = m1 = int.minValue; // store for case when only three values
for(i = 0; i < a.length; i++) {
m = a[i];
if      (m > p3) { p1 = p2; p2 = p3; p3 = m; }
else if (m > p2) { p1 = p2; p2 = m; }
else if (m > p1) { p1 = m; }
else if (m < n2) { n1 = n2; n2 = m; }
else if (m < n1) { n1 = m; }
switch (i)
case 1 : m1 = m; break;
case 2 : m2 = m; break;
case 3 : m3 = m; break;
}
l = a.length;
if (l < 3)                  { v = 0; } // error?
else if (l == 3)            { v = m1 * m2 * m3; }
else if (n1 * n2 > p1 * p2) { v = n1 * n2 * p3; }
else                        { v = p1 * p2 * p3; }
return v;

把它看作是伪代码，而不是真正的Java。

https://www.online-python.com/Hreut5EWav

下面本质上是QuincyJones的更紧凑的逻辑，但没有排序操作。我减少了一个单元格中涉及的变量的数量

n1 = n2 = 0; // two smallest negatives
m3 = m2 = m1 = int.minValue; // three largest values regardless of sign
for(i = 0; i < a.length; i++) {
m = a[i];
if      (m > m3) { m1 = m2; m2 = p3; m3 = m; }
else if (m > m2) { m1 = m2; m2 = m; }
else if (m > m1) { m1 = m; }
if      (m < n2) { n1 = n2; n2 = m; }
else if (m < n1) { n1 = m; }
}
return m3 < 0 || n1 == 0 || n1 * n2 < m1 * m2 ?
m1 * m2 * m3 : n1 * n2 * m3;

https://www.online-python.com/FufUN9vAEp