java - 我有一个算法，但不知道它如何工作或为什么工作

Question

任务是这样的：两个朋友各有一套巧克力板。各个板块的大小以元素类型 int 的数组形式提供。由于两人是非常要好的朋友，他们计划交换一块巧克力，以使两者总体拥有相同数量的巧克力。

您的方法应该返回一个长度为 2 的数组。第一个和第二个元素分别记录第一个和第二个朋友的平板大小，以实现此目标。

如果有几种可能的解决方案，您可以退回其中任何一种。

良友：示例1 无结果 参数：A = {1,1}, B = {2,2} 返回值：{1,2}

良友：例2无结果参数：A = {1,2}, B = {2,3} 返回值：{1,2}

Fair Friends: Example 3 No results 参数：A = {2}, B = {1,3} 返回值：{2,3}

Faire Freunde: Beispiel 4 无结果 参数：A = {1,2,5}, B = {2,4} 返回值：{5,4}

这是代码：

public static int arraySum(int[] a){
    int result = 0;
    for(int i = 0; i<a.length; i++){
        result+=a[i];
    }
    return result;
}

public static int[] fairFriends(int[] arr, int[] arr2) {
    int[] result = new int[2];
    int sum1 = arraySum(arr);
    int sum2 = arraySum(arr2);
    int sub = sum1 - sum2;
    for(int i = 0; i<arr.length; i++){
        for(int j = 0; j < arr2.length; j++){
            if(sub/2 == arr[i] - arr2[j]){
                result[0] = arr[i];
                result[1] = arr2[j];
            }
        }
    }
    
    return result;
}

这是我的队友发给我的。我试图仔细考虑代码，但在计算中我真的不明白为什么这会起作用......我只是想要一个解释。

标签： javaalgorithm

Answer 1

A = {2}, B = {1,3} 返回值：{2,3}

让我们先把这个例子分开。

交换前，A 的巧克力总量为 2，B 有 4 个（1+3）。

然后，发生交换：A 将其 2 尺寸的平板转移到 (A 减去 2 并将 B 加 2，所以它们现在位于{0, 6}，然后 B 转移它们的 3 尺寸的平板，因此从 B 中减去 3 并将 3 加到答：{3, 3}，这是平衡的，因此{2, 3}是正确的答案。

显然，一种相当低效的策略是模拟 A 拥有的每一个单块与 B 拥有的每一个最后一个单块的交换，并返回我们碰巧偶然发现导致最终结果平衡的交换的那一刻。

这正是您的算法所做的：它为 A 和 B 交换所有可能的平板，直到找到命中：

int sum1 = arraySum(arr);

sum1是 A 的巧克力储备的大小，预先交换。在我们的示例中，2。

int sum2 = arraySum(arr2);

sum2是 B 的巧克力储备的大小，预先交换。在我们的示例中，4。

int sub = sum1 - sum2;

A 有多少巧克力与 B 有多少之间的差异（-2意思是：B 比 A 多 2 块巧克力）。这意味着这个数字的一​​半需要从 A 流到 B 以达到平衡（在这个例子中，所需的流是-1：1 块巧克力的净需要从 B 流到 A，那么我们就有了平衡）。不过，“一半”部分稍后会出现 - 在这里做会更容易阅读和更有效/2。

for(int i = 0; i<arr.length; i++){ for(int j = 0; j < arr2.length; j++){

双嵌套循环；i/j 将涵盖所有潜在的交换。这增长很快。如果 A 有 10 块巧克力，B 有 20 块巧克力，那么有 200 种可能的交换，这个结构将考虑所有交换。

if(sub/2 == arr[i] - arr2[j]){

我们选择了 A 的一块板子送给 B（第 i 个板子），并选择了 B 的一块板子送给 A（第 j 个板子）。所以，让我们得到 A 的第 i 个平板arr[i]的大小 ( ) 和 B 的第 j 个平板的大小 ( arr2[j])，并检查差异。在我们的示例中（请记住，开始时是 A={2}，B={1,3}），正确的交换是 i=0（A 的 2 尺寸的平板）和 j=1（B 的 3 尺寸的平板） . 2-3是 -1，如，这是巧克力的净“流量”，其中 1 从 B 流向 A（如果为正，则从 A 流向 B）。这是我们想要的，这里/2出现了。我们的sub值是-2，它除以 2，因此-1等于 ，等于arr[i] - arr2[j]。如果这个if块成功，我们找到了一个可以工作的交换：然后代码设置result，否则，什么也不做，尤其是继续前进，即使我们已经有了答案——这只是这个特定的算法不好。

然后，result返回，顺便说一句，这也意味着如果不可能交换，算法返回“A应该用B的第一个slab交换他们的第一个slab”，即如果不能交换，则直接向上的代码是错误的。我猜这个练习并不关心你的代码是否会因为无法交换而给出错误的答案而失败。

有更有效的方法可以做到这一点，但它们会涉及编写更多代码。例如，您可以先按大小对 A 的平板和 B 的平板进行排序（即 2 次O(nlogn)操作），然后遍历 A 的平板 ( O(n))，并为每个平板计算 B 的平板必须有多大才能使交换完美。如果它是负数，continue;立即到 A 的下一个平板。否则，使用二分查找来检查 B 是否具有所需大小的平板。二分查找是O(logn). 如果是，则返回正确的结果，如果不是，则继续 A 的下一个平板。

那就是2*O(n logn) (O(n) * O(log n))，归结为O(nlogn)，而您的算法是O(n^2)。

这意味着，如果您通过绘制“两个朋友拥有的平板数”与“算法完成计算结果所需的时间”来绘制这两种算法的性能图，那么您的算法看起来y=x^2像like y=x * log(x)，因此如果输入足够大，“我的”算法最终会更快，而且明显更快。

通常使用这样的算法练习，重点是找到最有效的算法，并且对于（通常相当大的）测试输入花费太长时间的正确代码仍然被视为失败。

这可能不是这里的情况，但是，告诉你一个更有效的算法似乎是恰当的。