解释算法背后的数学原理

Question

给定一个已排序的整数数组 a，找到这样一个整数 x，它的值是

abs(a[0] - x) + abs(a[1] - x) + ... + abs(a[a.length - 1] - x) 是可能的最小值（这里 abs 表示绝对值）。如果有多个可能的答案，则输出最小的一个。

例子

对于 a = [2, 4, 7]，输出应为 absoluteValuesSumMinimization(a) = 4。

我能够通过蛮力解决这个问题，但后来我发现了这个

function absoluteValuesSumMinimization(A) {
    return A[Math.ceil(A.length/2)-1];
}

希望了解这是如何/为什么起作用的。

Answer 1

让我们来分解一下。

A.length/2返回长度的一半，用于查找数组的中间位置。对于偶数长度数组，这将位于中间的右侧。对于奇数长度的数组，它将位于中间。

Math.ceil(A.length/2)必要时向上舍入，因此 5 的数组的中间位置将是 2.5 -> 3。这使得奇数长度数组减少 1。

Math.ceil(A.length/2)-1下降一个指数。这可以纠正所有阵列的相差一错误。

所有这个解决方案的意思是，在偶数长度的数组中，您要查找的值将始终位于中间的左侧。在奇数长度的数组中，它始终是中间项。

这在直觉上是有道理的。从每个项目中减去数组中的中间项目将始终得到最低的总和。在偶数长度数组中，两个中心项将始终产生相同的总和，因此最小的数字将位于中心的左侧。

要看到这一点，请console.log从这个暴力解决方案中删除注释并尝试几个数组：

function absoluteValuesSumMinimization(ints) {
  const vals = [];

  ints.forEach(int => {
    const sum = ints.reduce((accum, next) => {
      return accum + Math.abs(next  - int);
    }, 0);

    vals.push(sum);
  });

  // console.log(vals);
  const lowest = Math.min(...vals);
  return ints[vals.indexOf(lowest)];
}