我有一个无向图,表示 Facebook 等社交媒体中的用户连接。
有N个节点,从1到N
边由数组 from 和 to 表示。
任务数组表示我有兴趣查找该节点(即社交媒体中的用户)的连接的节点号。
Example:
N = 5
From = [2,2,1,1]
To = [1,3,3,4]
Task = [4,2,5]
Answer:
[4,4,1]
解释:
该图如下所示:
Now for Task [4,2,5]
4 -> [1,2,3,4] The node 4 has these connections
2 -> [1,2,3,4] The node 2 has these connections
5 -> [5]
所以结果是 [4,4,1]
限制条件:
N=2 to 10^5
size of arrays from, 'to', and tasks is 2 to 10^5
这是一个黑客级别的问题。我的代码在 15 个测试用例中有 8 个失败,表示大输入出现超时错误。
这是我的代码:
public static List<Integer> solve(int N, List<Integer> from, List<Integer> to, List<Integer> tasks) {
int n = from.size();
// Create the graph
Map<Integer, Set<Integer>> map = new HashMap<>();
for(int i=0; i<n; i++) {
int key1 = from.get(i);
int key2 = to.get(i);
Set<Integer> value = map.getOrDefault(key1, new HashSet<>());
value.add(key2);
map.put(key1, value);
value = map.getOrDefault(key2, new HashSet<>());
value.add(key1);
map.put(key2, value);
}
List<Integer> result = new ArrayList<>();
for(int node: tasks) {
result.add(bfs(map, node));
}
return result;
}
// Solve using breadth first search approach
public static int bfs(Map<Integer, Set<Integer>> map, int node) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> q = new LinkedList<>();
int count = 0;
visited.add(node);
q.add(node);
while(!q.isEmpty()) {
node = q.poll();
count++;
Set<Integer> val = map.get(node);
if(val != null) {
for(int next : val) {
if(visited.add(next)) {
q.add(next);
}
}
}
}
return count;
}
我也尝试了递归方法,仍然存在同样的问题,对于较大的输入大小值,我遇到超时错误。
如何降低这段代码的时间复杂度。