javascript - 解释算法背后的数学原理

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。这使得奇数长度的数组减一.

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)];
}