在Java中找到n个数组之间的公共元素之和 [英] Finding the sum of common elements between n number of arrays in java

问题描述

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

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

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

  import java.util.Scanner; 
 
公共类示例{
 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]）; 
} 
} 
} 
} 
} 
  

解决方案

实际上有一个更通用的方法，它还能回答问题如何在运行时更改循环数？。

一般问题

我们正在寻找一种实现与之等效的方法：

< （i1 = 0; i1 对于（i2 = 0; i2 对于（i3 = 0; i3< k3; i3 ++）{
...
for（in = 0; in< kn; in ++）{
f（x1 [i1]，x2 [i2] ，... xn [in]）;
}
...
}
}
}


其中， n 是在运行时给出的，而 f 是使用<$列表的函数c $ c> n 参数，处理当前的n元组。

一般解决方案

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

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

 无效过程（int idx，int n，int [] [] x，int [] k，Object [] ntuple）{ 
 if（idx == n）{
 //我们有一个完整的n元组，​​
 //带有n个数组中的每个数组的元素
f（ntuple）; 
的回报； 
} 
 
 //这是第idx个 for语句
 for（int i = 0; i< k [idx]; i ++）{
 ntuple [idx] = x [idx] [i]; 
 //通过此递归调用，我们确保
 //我们还生成for的
过程的其余部分（idx + 1，n，x，k，ntuple）； 
} 
} 
  

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

process（0，n，x，k，new Object [n]）;

实际考虑

上述解决方案具有很高的复杂性（它是O（k ₁ ⋅k ₂ ⋅..⋅ k _n ）），但有时可以避免进行最深循环。

实际上，在本文中提到的特定问题（需要汇总所有数组中的公共元素）中，我们可以跳过生成一些元组 eg 如果已经x ₂ [i ₂ ]≠x ₁ [i ₁ ]。

在递归解决方案中，可以轻松修剪这些情况。此问题的特定代码可能如下所示：

  void进程（int idx，int n，int [] [] x，int [] k，int value）{
 if（idx == n）{
 //来自当前元组的所有元素都等于 value。 
 //将其添加到全局 sum变量中
 sum + = value; 
的回报； 
} 
 
 for（int i = 0; i< k [idx]; i ++）{
 if（idx == 0）{
 //这是外部 for，设置新值
 value = x [0] [i]; 
} else {
 //检查idb的当前元素是否与
具有相同的值，如果（x [idx] [i ] == value）{
 process（idx + 1，n，x，k，value）; 
} 
} 
} 
} 
  

I have a program that sums the common elements of two arrays. For that I used two for loops and if I have three then I could use three for loops. But how to sum the common elements of n number of arrays where n is coming during run time.

I don't know how to change the number of loops during run time or is there any other relevant concept for this ?

Here is the code I've tried for summing twoarrays:

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]);
                }
            }
        }
    }
}

解决方案

There is actually a more general method, that also answers the question "how to change the number of loops during run time?".

The general question

We are looking for a way to implement something equivalent to this:

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]);
         }
       ...
     }
   }
 }

where, n is given at runtime and f is a function taking a list of n parameters, processing the current n-tuple.

A general solution

There is a general solution, based on the concept of recursion.

This is one implementation that produces the desired behavior:

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);
    }
}

The function assumes that the n arrays are stored in a matrix x, and the first call should look like this:

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

Practical considerations

The solution above has a high complexity (it is O(k₁⋅k₂⋅..⋅k_n)), but sometimes it is possible to avoid going until the deepest loop.

Indeed, in the specific problem mentioned in this post (which requires summing common elements across all arrays), we can skip generating some tuples e.g. if already x₂[i₂] ≠ x₁[i₁].

In the recursive solution, those situations can easily be pruned. The specific code for this problem would probably look like this:

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个数组之间的公共元素之和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！