这是解决数组分区问题的正确方法吗？

Question

我在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

还有另一个测试用例输入= [1、1、2、2]，期望输出为3？

如果我使用上面编写的相同函数，则会创建一对（1,2），（1，2）=> 1 + 1 =2。但是他们现在期望这对（（1,1），（2 ，2）=> 1 + 2 = 3。

如何解决这个问题？我在这里想念什么吗？

Answer 1

技巧是首先对数组进行排序，然后对每个具有偶数索引的数字求和（即每对中最小的数字）。

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上测试：

Answer 2

[当您取最小的2个数字时，对中的较大数字对我们来说就无关紧要了，因此我们的目标是确保每个对都尽可能地接近，这可以通过sorting来实现，并且只需在奇数中添加元素即可位置。

let arrSum = (arr) => arr.sort().filter((d, i) => i % 2 == 0).reduce((a, b) => a + b)


console.log(arrSum([1, 2, 3, 4]))
console.log(arrSum([1, 1, 2, 2]))

Answer 3

数字越接近，则取最小值时损失的越少。对数组进行排序，然后对数据块进行排序，并对最小值进行求和（每对的第一项）。

const chunk = (size, arr) => Array.from(
  { length: Math.ceil(arr.length / size) }, 
  (_, i) => arr.slice(size * i, size * (i + 1))
)

const sunMin = (size, arr) =>
  chunk(size, [...arr].sort())
  .reduce((s, [n]) => s + n, 0)
  
console.log(sunMin(2, [1, 2, 3, 4]));
console.log(sunMin(2, [1, 2, 1, 2]));