查找数组中两个不同数字之间的最大乘积。该产品还必须是 3 的倍数

Question

下面的代码找到了最大的乘积对，但仍然不能确定数字是否不同以及乘积是 3 的倍数。

令 arr = [1, 4, 3, 6, 9, 9];

例如，上述数组的答案应该是 9x6=54（最大不同数的乘积也是 3 的倍数）但我当前的代码结果是 9x9=81.

重要的观察，给定的数组也可以包含正数和负数。

有人有什么建议吗？

// product in array of Integers
function maxProduct(arr, n)
{
     
    // Sort the array
    arr.sort(function(a, b){return a - b});
     
    let  num1, num2;
     
    // Calculate product of two smallest numbers
    let sum1 = arr[0] * arr[1];
     
    // Calculate product of two largest numbers
    let sum2 = arr[n - 1] * arr[n - 2];
     
    // print the pairs whose product is greater
    if (sum1 > sum2)
    {
        num1 = arr[0];
        num2 = arr[1];
    }
    else
    {
        num1 = arr[n - 2];
        num2 = arr[n - 1];
    }
    document.write("Max product pair = " +
                 "{" + num1 + "," + num2 + "}");
}

</script>

Answer 1

一个O(N)次，O(1)额外的space算法：

遍历数组，跟踪两个变量：max_multiple_of_three和min_multiple_of_three
遍历数组，跟踪两个变量：largest_number_in_array（不应等于max_multiple of three）和smallest_number_in_array（不应等于min_multiple_of_three)
答案将是 max_multiple_of_three * largest_number_in_array 或 min_multiple_of_three * smallest_number_in_array

Answer 2

你可以这样做：

将数组拆分为 multiples_of_3 (M3) 和 non_multiples_of_3 (NM3)。
从 M3 和 NM3 中找出前 2 个最大的数字。您的答案将始终包含最大的 M3。
请注意，您的用例需要不同的最大数字。这需要照顾。例如。在python中，您可以将输入列表转换为集合等
求出剩余3个中最大的数

这将始终适用于正数数组。如果也有 -ve 个数字，那么，只有 selected 都是 -ve，-ve 个数字才会成为解决方案的一部分。在这种情况下，您可以仅对输入中的 -ve 个数字重复这些步骤并进行比较。

复杂度：O(n)：2 次遍历，一次将数组拆分为 M3 和 NM3，然后是 select 最大的 M3 和其他 3 个 +ve 和 -ve 值的候选对象。

查找数组中两个不同数字之间的最大乘积。该产品还必须是 3 的倍数

Find the maximum product between two different numbers in an array. The product also has to be a multiple of 3

arrays

sorting

algorithm

integer