javascript - 在分布式环境中拆分数组以找到两个子数组之和之间的最小差异

Question

这个问题我昨天被问到了。我必须编写一个代码将数组分成两部分，以便这两部分之和之间的差异最小。

这是我编写的复杂度为O(n)的代码

function solution(a) {
  let leftSum = 0;
  let rightSum = a.reduce((acc, value) => acc + value ,0);
  let min = Math.abs(rightSum - leftSum);
  a.forEach((item, i) => {
   leftSum += a[i];
   rightSum -= a[i]; 
   const tempMin = Math.abs(rightSum - leftSum);
   if(tempMin < min) min = tempMin;
  })
  return min;
}

但是后来有人问我输入数组的长度是否为1000万，我将如何在分布式环境中解决这个问题？

我是分布式编程的新手，需要帮助。

标签： javascriptalgorithmdistributed-computingdistributeddistributed-system

Answer 1

如果您有N节点，则将数组拆分为N顺序子数组；这将为您提供N连续的总和。通过一次来确定哪个子数组包含所需的分割点。“之前”和“之后”总和之间的差异是您下一阶段的偏差目标......

现在将该“中间”数组分成N几部分。再次，您寻找合适的分割点，除了现在您知道您想要的确切结果（因为您有数组总和和缺失的差异）。

重复第二段，直到您可以将整个子数组放入一个节点，这是完成项目计算的最快方法。

---

您可以通过在每个值处保持累积和来加快速度；这将允许您在每个阶段更快地找到适当的分割点，因为您可以在第一个阶段之后对每个阶段使用二进制或插值搜索。