java查找三个数组中至少两个数组中的数字

Question

我可以如何解决以下问题：

Create an array of integers that are contained in at least two of the given arrays.

例如：

int[] a1 = new int[] { 1, 2, 3, 4, 5 };          
int[] a2 = new int[] { 5, 10, 11, 8 };           
int[] a3 = new int[] { 1, 7, 6, 4, 5, 3, 11 };

必须给出一个结果数组

int[] result = new int[] {1, 3, 4, 5, 11}

另外，我感兴趣的是关于如何处理这个（“算法”）的建议，而不是Java UTIL可能给我的答案

Answer 1

从数学上讲，这可以通过以下方式解决：

可以使用三个数组中的每一个来构造三个集合，因此每个数组中的重复条目在每个集合中只出现一次。然后，至少出现在三个集合中的两个集合中的条目就是解决方案。所以它们是由

(S_1 intersect S_2) union (S_2 intersect S_3) union (S_3 intersect S_1)

Answer 2

你可以把这3个数组看作sets，然后找到一些集合的intersection中的每个元素

基本上，你在寻找(set1 [intersection] set2) [union] (set2 [intersection] set3) [union] (set1 [intersection] set2)

我同意这可能不是实现你所追求的目标的最简单的方法，但是能够将一个问题简化为另一个问题是每个程序员都应该掌握的一种技巧，这个解决方案应该是非常有教育意义的

Answer 3

1. 将a1数字放入Map<Integer,Integer> count，使用该值作为键，并将计数设置为1
2. 把a2个数字放在同一张地图上。如果一个项目不存在，则分配1的计数，否则分配现有计数+1
3. 把a3个数字放在同一张地图上。如果一个项目不存在，则分配1的计数，否则分配现有计数+1
4. 检查映射中的条目，并输出值大于1的所有键

该算法在三个阵列中的元素总数中摊销线性时间

如果这三个数组中的数字被限制为（比如）1000或另一个相对较小的数字，则完全可以避免使用集合，但根据数字的上限使用一个可能更昂贵的算法：用数组counts[MAX_NUM+1]替换映射，然后运行相同的算法，如下所示：

int[] counts = new int[MAX_NUM+1];
for (int a : a1) counts[a]++;
for (int a : a2) counts[a]++;
for (int a : a3) counts[a]++;
for (int i = 0 ; i != MAX_NUM+1 ; i++) {
    if (counts[i] > 1) {
        System.out.println(i);
    }
}

Answer 4

我喜欢画维恩图解。你知道有三个相交圆的图，例如，参见here

然后你会发现补语更容易描述： 那些只存在于一个数组中的元素并不有趣

因此，您可以在散列映射中构建一个频率列表（即key=element，value=count，在多少个数组中您[第一次]找到了它），然后在最后一次传递中选择所有出现多次的元素

为了简单起见，我使用了集合。如果数组包含多个相同值的条目，则在构建频率列表时必须忽略这些额外发生的事件

Answer 5

思考一下这个问题以及你可能会使用的不同策略：

1. 检查每个数组中的每个条目，如果该条目不在“duplicates”结果中，则查看该条目是否在剩余的每个数组中。如果是，则添加到重复项，并返回到下一个整数
2. 通过从每个数组中添加一个条目（如果已经存在条目，则将其放入duplicates数组），创建一个非重复条目数组
3. 使用你自己的另一个创造性策略

Answer 6

在没有集合的情况下，实现这一点的唯一方法是从一个数组中提取一个元素，迭代剩余的两个数组，查看是否找到了重复的元素（然后断开并移动到下一个元素）。你需要对三个数组中的两个这样做，因为当你移动到第三个数组时，你已经得到了答案