leetcode.com 给我的问题
问题陈述:
给定一个包含 2n 个整数的数组，你的任务是将这些整数分组为 n 对整数，比如 (a1, b1), (a2, b2), ..., (an, bn) 使得总和为 min (ai, bi) 对于从 1 到 n 的所有 i 尽可能大。
示例 1: 输入:[1,4,3,2]
输出:4
解释:n为2，最大对数和为4 = min(1, 2) + min(3, 4)。
注意: n为正整数，取值范围为[1, 10000]。 数组中的所有整数都在 [-10000, 10000] 范围内。
我尝试使用下面的 javascript 代码解决这个问题
// NOTE: This is more optimal and can work
function chunkWithoutIndex(inputArr, partition) {
let length = inputArr.length;
let sliced = [];
let count = 0;
for (let i = 0; i <= length - 1; i++) {
let subArr = sliced[count];
if (!subArr) {
sliced[count] = [];
}
let subArrLen = sliced[count].length;
if (subArrLen !== partition) {
sliced[count].push(inputArr[i]);
} else {
count++;
sliced[count] = [inputArr[i]]
}
}
return sliced;
}
// NOTE: This does not consider the chunk size
function checkWithTwoPointers(inputArr) {
let length = inputArr.length;
let left = 0;
let right = length - 1;
let sliced = [];
while (left <= right) {
if (left !== right) {
sliced.push([inputArr[left], inputArr[right]]);
} else {
sliced.push([inputArr[left] || inputArr[right]]);
}
left++;
right--;
}
return sliced;
}
function arrayPartition(inputArr, partition) {
// let sliced = chunkWithoutIndex(inputArr, partition);
let sliced = checkWithTwoPointers(inputArr);
let sum = 0;
let slicedLen = sliced.length;
for (let i = 0; i <= slicedLen - 1; i++) {
sum = sum + Math.min(...sliced[i]);
}
return sum;
}
在提交问题进行验收时，由于不同的测试用例，我遇到了失败。
看到测试用例在输入 = [1, 4, 3, 2] 时运行良好，期望输出为 4。 所以配对将是
(1, 4) , (3, 2) = 1 + 2 = 3
(1, 3), (4, 2) = 1 + 2 = 3
(1, 2), (4, 3) = 1 + 3 = 4 --> Selected Pair
还有一个测试用例 input = [1, 1, 2, 2] ，它期望输出为 3？
如果我使用上面写的相同函数，它将创建一对 (1,2) , (1, 2) => 1+ 1 = 2。但他们现在期待这对 (1,1), ( 2, 2) => 1 + 2 = 3。
如何解决这个问题？我在这里遗漏了什么吗？
最佳答案
诀窍是先对数组进行排序，然后对索引为偶数的每个数字求和(即每对中最小的数字)。
var arrayPairSum = function(nums) {
nums.sort((a, b) => a - b);
let sum = 0;
for(let i = 0; i < nums.length; i += 2) {
sum += nums[i];
}
return sum;
};
在 LeetCode 上测试:
关于javascript - 这是解决数组分区问题的正确方法吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58596726/