主页 / coding / 问题 / 79019383
Accepted
arlovande
Asked: 2024-09-24 23:41:13 +0800 CST

寻找数组的最佳划分

  • 772

我正在尝试在Apps Script中编写一个函数来获取一个大型值数组，我希望将其尽可能均匀地拆分为值的子数组（数组的数组）。每个子数组的长度最好为 15 个值。每个数组中的最大值数为 20，最小值数为 10。

如果数组的值为 21，则将有一个数组 10 和一个数组 11。22 将是两个数组 11。依此类推，直到得到 36 (18, 18)。在 37 时，您将得到 (13, 13, 14)。38 将是 (13, 14, 14)

我最初的想法是取起始数字并找到最接近 15 的倍数。因此，如果数字是 47，则 45 是最接近的倍数。如果最接近的倍数小于起始数字，则使用该倍数的因数，然后计算起始数字和倍数之间的差值。将该数字分配到每个数组中，直到达到差值和。因此 45 是 3 的因数。这意味着 3 个数组都是 15，那么 47 和 45 之间的差值就是 2。因此，将第一个数组加一，将第二个数组加一，得到 16、16、15。

如果较接近的倍数高于起始数字，则使用较高倍数的因数，然后计算起始数字和较高倍数之间的差值，从每个子数组中减去一，直到用尽该差值。因此，对于 43，较高倍数是 45 (15, 15, 15) 较高数字之间的差值为 2，因此从前两个数组中减去 1 并得到 (14, 14, 15)。

到目前为止，我有这个，它会告诉我每个数组应该有多少个值。但它在数字 21 和 22 上失败了。我需要一些东西来获取每个数组中的值的数量，X 或 Y，并将 X 或 Y 值填充到该数组中。最终输出是一个数组数组，当从左到右读取时，它将保持与原始数组相同的顺序，尽管细分为数组。

function splitList(values) {
  const total = values.length;
  const optimalSize = 15;
  const minSize = 10;
  const maxSize = 20;

  if (total <= maxSize) {
    return [values];
  }

  let numSublists = Math.round(total / optimalSize);
  let sublistSize = Math.floor(total / numSublists);
  let remainder = total % numSublists;

  let result = [];
  let startIndex = 0;

  for (let i = 0; i < numSublists; i++) {
    let currentSize = sublistSize + (remainder > 0 ? 1 : 0);
    result.push(values.slice(startIndex, startIndex + currentSize));
    startIndex += currentSize;
    remainder--;
  }

  return result;
}

// Example usage:
const values = Array.from({
  length: 43
}, (_, i) => i + 1);
const sublists = splitList(values);
console.log(sublists);

javascript

1 个回答

  1. Best Answer

    算法中的主要问题出现在子列表数量较少时，此时子列表数量不足以分配值(total % optimalSize)而不会超出最大大小限制。

    在循环之前添加以下代码for应该可以解决问题：

    // If the sublists exceed the maximum allowed size,
while (sublistSize > maxSize) {
  // use one more sublist.
  numSublists++;
  // Recompute the variables.
  sublistSize = Math.floor(total / numSublists);
  remainder = total % numSublists;
}

    但是，我不认为您的方法是最佳的。事实上，四舍五入total / optimalSize并不能优化子列表的大小。例如，对长度为 37 的初始数组运行您的算法会将其细分为长度为 19 和 18 的两个子数组，而不是长度为 12、12、13 的三个子数组。

    我建议替换这个：

    let numSublists = Math.round(total / optimalSize);
let sublistSize = Math.floor(total / numSublists);
let remainder = total % numSublists;

    ；这样：

    let numSublists = Math.floor(total / optimalSize);
if ((total % optimalSize) / numSublists > (optimalSize - (total % optimalSize)) / (numSublists+1)) {
  numSublists++;
}
let sublistSize = Math.floor(total / numSublists);
let remainder = total % numSublists;

    添加的if语句决定是否使用其中一种numSublists = Math.floor(total / optimalSize)，或者numSublists = Math.ceil(total / optimalSize)通过比较两种情况下子列表大小与最佳大小的平均超额/不足来决定。

    如果你这样做，你会发现你不需要while我之前提到的循环。

    我对我的答案并不完全有信心——我还没有尝试证明这一点——但我相信它应该有效。我相信有更好、更优雅的方法来做到这一点，但为此我们必须等待其他答案:p

    • 0

相关问题