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

Question

输入是两个数组，每个数组的长度为 6，数组中的每个元素都可以是 [1, 2, 3, 4, 5, 6] 中的某个数字。 .返回最小数量以更改数组以使两个数组的总和相等。
例如，A = [5, 4, 1, 2, 6, 5] , B = [2] ;返回 6 因为我们可以在 A 中掷五个骰子获取 [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

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

确定哪些数组的总和较大，哪些较小

可选:对数组进行排序以加快以下步骤

虽然总和不一样:

从较大的数组中获取最大元素，从较小的数组中获取最小元素

确定哪个具有更大的“潜力”来均衡总和，例如5在“更大”的数组中可以更改为 1 ，或 3在较小的数组中可以更改为 6

选择具有更多“潜力”的元素并更改它(一直到 1 或 6，或根据需要)

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