求 java 中 n 个数组之间公共元素的总和

Question

我有一个程序可以对两个数组的共同元素求和。为此，我使用了两个 for 循环，如果我有三个，那么我可以使用三个 for 循环。但是如何对 n 个数组的公共元素求和，其中 n 在运行时间内出现。

我不知道如何在运行时间内更改循环次数，或者是否有任何其他相关概念？

这是我尝试对两个数组求和的代码：

import java.util.Scanner;

public class Sample {
    public static void main(String... args)
    {
        Scanner sc=new Scanner(System.in);
        int arr1[]={1,2,3,4,5},arr2[]={4,5,6,7,8},sum=0;
        for (int i=0;i<arr1.length;i++)
        {
            for (int j=0;j<arr2.length;j++)
            {
                if (arr1[i]==arr2[j])
                {
                    sum+=(arr1[i]);
                }
            }
        }
    }
}

Answer 1

假设元素的索引不重要：a[1] = 2 和a[5] = 2，你只需要两个嵌套循环。

首先，您需要将 n-1 个数组放入集合列表中。然后遍历第 n 个数组并检查列表中的所有集合中是否存在每个元素。如果确实存在，则添加到总数中。

Answer 2

可以有不同的实现方式。您可以使用以下方法。这是伪代码

使用二维数组来存储数组。如果数组的数量是 n 并且大小是 m 那么数组将是 input[n][m]
用一个ArrayList commonItems来存放常用的物品。用 input[0]
现在遍历 i = 1 to n-1 的数组。与每个 input[i] 比较，在每一步只存储 commonItems 和 input[i] 的共同项。您可以通过将 input[i] 转换为列表并使用 retainAll 方法来实现。
在迭代结束时，commonItem 列表将仅包含常用数字。现在求和这个列表的值。

Answer 3

实际上有一个更通用的方法，它也回答了问题 "how to change the number of loops during run time?"。

一般问题

我们正在寻找一种方法来实现与此等效的东西：

for (i1 = 0; i1 < k1; i1++) { 
  for (i2 = 0; i2 < k2; i2++) {
    for (i3 = 0; i3 < k3; i3++) {
       ...
         for (in = 0; in < kn; in++) {
           f(x1[i1], x2[i2], ... xn[in]);
         }
       ...
     }
   }
 }

其中，n 在运行时给出，f 是一个采用 n 参数列表的函数，处理当前的 n 元组。

通用解决方案

有一个通用的解决方案，基于递归的概念。

这是一种产生所需行为的实现：

void process(int idx, int n, int[][] x, int[] k, Object[] ntuple) {
    if (idx == n) {
        // we have a complete n-tuple, 
        // with an element from each of the n arrays
        f(ntuple);
        return;
    }

    // this is the idx'th "for" statement
    for (int i = 0; i < k[idx]; i++) {
        ntuple[idx] = x[idx][i];
        // with this recursive call we make sure that 
        // we also generate the rest of the for's
        process(idx + 1, n, x, k, ntuple);
    }
}

该函数假定 n 数组存储在矩阵 x 中，第一次调用应如下所示：

process(0, n, x, k, new Object[n]);

实际考虑

上面的解复杂度很高（是O(k₁⋅k₂⋅..⋅k_n))，但有时可以避免进入最深的循环。

的确，在这个post中提到的特定问题（需要对所有数组的公共元素求和），我们可以跳过生成一些元组例如如果已经x ₂[i₂]≠x₁[i₁].

在递归解决方案中，这些情况很容易被删减。这个问题的具体代码大概是这样的：

void process(int idx, int n, int[][] x, int[] k, int value) {
    if (idx == n) {
        // all elements from the current tuple are equal to "value". 
        // add this to the global "sum" variable
        sum += value;
        return;
    }

    for (int i = 0; i < k[idx]; i++) {
        if (idx == 0) {
            // this is the outer "for", set the new value
            value = x[0][i];
        } else {
            // check if the current element from the idx'th for
            // has the same value as all previous elements
            if (x[idx][i] == value) {
                process(idx + 1, n, x, k, value);
            }
        }
    }
}

求 java 中 n 个数组之间公共元素的总和

Finding the sum of common elements between n number of arrays in java

java

arrays

algorithm

data-structures

array-algorithms

一般问题

通用解决方案

实际考虑