java - 找到4个元素的共同元素

我有一个映射TreeMap<Integer, Set<Integer>> adjacencyLists和一个整数集TreeSet<Integer> specialNodes。

该图表示图的邻接表。

我想从adjacencyLists中选择键，然后在specialNodes中查找它们是否存在共同的邻接点。

有没有办法有效地做到这一点？

例：

adjacencyLists如下：

[1, [2 3 4 5]]
[2, [1 5]]
[3, [1 4 5]]
[4, [1 3]]
[5, [1 2 3]]

specalNodes如下所示：

[1 3 4 5]

在此示例中，4和5出现在adjacencyLists的第一项和第三项的值中。

因此，编写函数findCommon(1,3)应该给我[4 5]
同样，findCommon(1,5)应该返回null，因为'2'是唯一的公用元素，并且不在specialNodes中。

最佳答案

因此，如果我理解正确，那么您已经为每个Integer设置了列出其邻接关系的集合吗？

我可以看到的最简单有效的方法是利用另一个Set。集合非常快速地检查它们是否已经包含值。

Set<Integer> adjacent = new HashSet<>();

for (Integer i: toCheck) {
   int oldCount = adjacent.size();
   Set<Integer> check = adjacencyLists.get(i);
   adjacent.addAll(check);
   if (adjacent.size() != oldCount+check.size()) {
      // Duplicate found
      return true;
   }
}
return false;

如果您需要知道公用的标识，则循环执行单个添加调用而不是执行addAll并检查每个添加是否成功。实际上，这可能更有效，因为不需要进行大小检查：

Set<Integer> adjacent = new HashSet<>();

for (Integer i: toCheck) {
   Set<Integer> check = adjacencyLists.get(i);
   for (Integer c: check)
      if (!adjacent.add(c)) {
         // Duplicate found
         return c;
      }
}
return null;

刚刚看到了对普通成员完整列表的要求：

Set<Integer> adjacent = new HashSet<>();
Set<Integer> results = new HashSet<>();

for (Integer i: toCheck) {
   Set<Integer> check = adjacencyLists.get(i);
   for (Integer c: check)
      if (!adjacent.add(c)) {
         // Duplicate found
         results.add(c);
      }
}
return results;