更改数组以使两个数组的总和相等的最短时间

Question

输入是两个数组，每个数组的长度最大为 6，数组中的每个元素可以是 中的某个数字[1, 2, 3, 4, 5, 6]。返回更改数组以使两个数组之和相等的最小数量。

例如，A = [5, 4, 1, 2, 6, 5]，B = [2]; 返回 6，因为我们可以将 5 个骰子投入，A得到[1, 1, 1, 1, 1, 1]，再投入 1 个骰子，B得到[6]；那么数组将具有相同的总和。

我的第一个想法是分别计算两个数组的总和：Sum(A) = 23, Sum(B) = 2。

然后蛮力方法是计算使总和等于 2, 3, 4, ..., 23 所需的更改。

但我觉得时间复杂度太高了。

这个问题的困难部分是我们不知道我们尝试合并的目标总和是多少。

尽管在给定的示例中，A 的最小和值为 6，但 B 的最大和值为 6，因此我们知道它们将在 6 处重叠，因此我们可以剪切其他分支。

Answer 1

贪心算法应该可以很好地解决这个问题：

\n

\n
• 确定哪个数组的总和较大，哪个数组的总和较小
\n
• 可选：对数组进行排序以使以下步骤更快
\n
• 虽然总和不一样:\n
  \n
  • 从较大的数组中获取最大元素，从较小的数组中获取最小元素
  \n
  • 确定哪个更有“潜力”来均衡总和，例如5“较大”数组中的 a 可以更改为1，或者 a3较小数组中的 a 可以更改为6
  \n
  • 选择具有更大“潜力”的元素并更改它（一直更改为 1 或 6，或根据需要）
  \n
  \n
\n

\n

重复查找最小和最大元素而无需排序的复杂度至多为 O(n\xc2\xb2)，并且可以通过对数组进行一次排序然后按顺序迭代元素将复杂度降低到 O(n logn)。（您不必对数组重新排序或重新计算总和，因为您知道哪些元素更改了多少，并且不必再次查看这些元素。）

\n