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

Question

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

map 表示图的邻接列表。

我想从 adjacencyLists 中选取 key 并查找它们在 specialNodes 中是否存在公共(public)相邻项.

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

示例:

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)。