java - 找到 4 个元素的公共(public)元素

Question

我有一张 map TreeMap<Integer, Set<Integer>> adjacencyLists和一个整数集 TreeSet<Integer> specialNodes .

map 表示图的邻接表。

我想从 adjacencyLists 中挑选 key 并在 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 中的常见元素.

Answer 1

这是一个循序渐进的过程。

1. 从键中获取两个值。 O(logn)。
2. 对它们进行排序。 O(nlogn)。
3. 找到 common elements . O(m+n)。
4. 在specialNodes 中搜索公共(public)元素。 O(m+n)。

因此最坏情况下的时间复杂度 = O(nlogn)。