0

我有一个 Java 计算问题，其中给了我一个整数数组：

例如：

3 -2 -10 0 1

我应该计算可以从这些整数中形成的最小整数和最大三元组。（在这种情况下，min=-30，max=60）

我最初认为最大值总是正数，最小值总是负数。

因此，

我最初的算法是：

  1. 扫描数组，取出里面最大的3个元素，存入一个数组。
  2. 同时取出里面最小的3个元素，存入另一个数组。

通过不等式，我们可以得出以下结论：

+ve = (-)(-)(+) 或 (+)(+)(+)

-ve = (+)(+)(-) 或 (-)(-)(-)

因此，我使用我计算的两个数组中的元素来尝试获得最大和最小三元组。（即为了得到最大的三元组，我比较了最大的3组成的三元组和最小的2和最大整数组成的三元组）

然而，我意识到如果所有给定的整数都是负数，我的算法就会失败，因为最大值是负数。（反之亦然）

我知道我可以简单地添加更多检查来解决这个问题，或者只是使用蛮力 O(N^3) 解决方案。但是必须有更好的方法来解决这个问题。

这个问题必须通过递归来解决，并且只能在 O(N) 时间内解决。

我正在修复中。有人可以指导我吗？

谢谢。

4

2 回答 2

1

如果您在线性时间内找到 3 个最大值和 2 个最小值，则存在 O(n) 解决方案。

但您也可以使用 nlog(n) 排序（即快速排序）轻松完成这项工作。

然后在这里找到C中最大乘积三元组的解决方案，并在评论中进行解释-

int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

int solution(int A[], int N) {

long product = A[0] * A[1] * A[2];
if (N == 3) {
    return product;
}

// Nlog(N)
qsort(A, N, sizeof(int), cmpfunc);

if (A[N - 3] >= 0) {
    // if there is at least 3 non-negative value
    // then take three maximum values
    product = A[N - 1] * A[N - 2] * A[N - 3];

    if (A[1] < 0) {
        // if there is at least 2 negative value
        if (product < A[N - 1] * A[0] * A[1]) {
            // then take maximum positive and two minimum negative, if that is more than 3 positive values
            product = A[N - 1] * A[0] * A[1];
        }
    }

} else if (A[N - 1] >= 0) { 
    // else if there is least 1 non-negative value
    // then take maximum positive and two minimum negative
    product = A[N - 1] * A[0] * A[1];

} else {
    // otherwise, take 3 maximum negative values
    product = A[N - 1] * A[N - 2] * A[N - 3];
}

return product;
}
于 2015-06-16T12:35:02.457 回答
0

首先，你只需要解决这两个问题之一，比如找到最大的三元积。有了这个，您可以通过对所有输入值求反，找到最大的三倍积，然后求反来找到答案。

所以让我们专注于寻找最大的。你已经做得很好了。首先取最大的正数（如果有的话）。然后选择两个最大的剩余正数对或两个最大（数量级）负数，以具有最大乘积的对为准。

如果根本没有正数，则选择三个最小的负数。

当然，这一切都可以在 O(n) 时间内完成，但这不是递归具有自然位置的算法。您必须使用微不足道的尾递归来代替循环。

于 2013-10-29T04:23:26.983 回答