我正在尝试用 JavaScript 编写一个有效的算法来解决这个任务。请参阅输入数据和正确结果的下一个示例:
Array: [ [-3,-4], [1,2,-3] ] Result: (-4)*(-3) = 12
Array: [ [1,-1], [2,3], [10,-100,20] ] Result: (-1)*3*(-100) = 300
Array: [ [-3,-15], [-3,-7], [-5,1,-2,-7] ] Result: (-15)*(-7)*1 = 105
它可以是任意数量的子数组和每个子数组中任意数量的元素。我已经发现我可能应该在每个子数组中只保留最小值和最大值,我使用 .map(a => [Math.min(...a), Math.max(...a)])
并使用 .sort((a, b) => a[0] - b[0])
对其进行排序.现在我被困住了。可能有一种方法可以计算所有可能的产品,但我确信这不是解决此任务的有效方法。
请帮忙!
最佳答案
您发布的问题可以通过简单的算法解决。我们只需要 继续跟踪最大值/最小值在遍历每个子数组时。我们可以通过将当前最大值/最小值与每个子数组中的最大值/最小值相乘来继续找到下一个最大值/最小值。我们选择最大值当迭代结束时。它的时间复杂度是O(n)
在哪里 n
是数组中的元素总数(即每个子数组中元素数的总和)。
这是完整的代码。 find_maximum_product
函数不断跟踪最小值/最大值并最终返回最大值,它还不断跟踪乘数并返回它:
/**
* arr: array of any number of sub-arrays and
* any number of elements in each sub-array.
* e.g. [[1, -1], [2, 3], [10, -100, 20]]
*/
function find_maximum_product(arr) {
let max = 1;
let min = 1;
let max_multipliers = [];
let min_multipliers = [];
for (let i = 0; i < arr.length; i++) {
const a = Math.max(...arr[i]);
const b = Math.min(...arr[i]);
const candidates = [max * a, max * b, min * a, min * b];
max = Math.max(...candidates);
min = Math.min(...candidates);
let new_max_multipliers;
let new_min_multipliers;
switch (max) {
case candidates[0]:
new_max_multipliers = max_multipliers.concat(a);
break;
case candidates[1]:
new_max_multipliers = max_multipliers.concat(b);
break;
case candidates[2]:
new_max_multipliers = min_multipliers.concat(a);
break;
case candidates[3]:
new_max_multipliers = min_multipliers.concat(b);
break;
}
switch (min) {
case candidates[0]:
new_min_multipliers = max_multipliers.concat(a);
break;
case candidates[1]:
new_min_multipliers = max_multipliers.concat(b);
break;
case candidates[2]:
new_min_multipliers = min_multipliers.concat(a);
break;
case candidates[3]:
new_min_multipliers = min_multipliers.concat(b);
break;
}
max_multipliers = new_max_multipliers;
min_multipliers = new_min_multipliers;
}
if (max >= min) {
return [max, max_multipliers];
}
return [min, min_multipliers];
}
const arrays = [
[
[-3, -4],
[1, 2, -3],
],
[
[1, -1],
[2, 3],
[10, -100, 20],
],
[
[-3, -15],
[-3, -7],
[-5, 1, -2, -7],
],
[
[14, 2],
[0, -16],
[-12, -16],
],
[
[-20, -4, -19, -18],
[0, -15, -10],
[-13, 4],
],
[
[-2, -15, -12, -8, -16],
[-4, -15, -7],
[-10, -5],
],
];
for (let i = 0; i < arrays.length; i++) {
const [max, max_multipliers] = find_maximum_product(arrays[i]);
console.log('Array:', JSON.stringify(arrays[i]));
console.log('Result:', `${max_multipliers.join(' * ')} = ${max}`);
console.log('');
}
更新
更简单的版本,只是获得最大值,而不是乘数:
/**
* arr: array of any number of sub-arrays and
* any number of elements in each sub-array.
* e.g. [[1, -1], [2, 3], [10, -100, 20]]
*/
function get_maximum_product(arr) {
return arr
.map((a) => [Math.min(...a), Math.max(...a)])
.reduce(
(acc, current) => {
const candidates = [
acc[0] * current[0],
acc[0] * current[1],
acc[1] * current[0],
acc[1] * current[1],
];
return [Math.min(...candidates), Math.max(...candidates)];
},
[1, 1]
)[1];
}
关于javascript - 找出每个子数组中任意一个元素可以形成的最大乘积,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63191064/