LeetCode 1311：BFS图遍历与视频频次统计实战

1. 题目解析与需求拆解

LeetCode 1311这道题描述了一个社交网络中的视频观看记录查询场景：给定一个用户的朋友关系网络和朋友观看的视频列表，要求找出指定层级好友观看的所有视频，并按观看频率和字母顺序排序输出。

这个题目本质上考察的是图遍历和数据处理能力。我们需要从起始用户出发，找到所有k层深度的好友（即广度优先搜索BFS的经典应用场景），然后统计这些好友观看的视频频次，最后按照题目要求的规则排序输出。

关键点提示：题目中的"k层好友"指的是最短距离为k的朋友，不是累计距离不超过k的所有朋友。这一点在BFS实现时需要特别注意。

2. 算法设计与实现思路

2.1 数据结构选择

首先我们需要选择合适的数据结构来表示题目中的各个元素：

1. 朋友关系图：使用邻接表表示最为合适，可以用vector<vector<int>>或者unordered_map<int, vector<int>>来存储
2. 视频记录：每个用户对应一个视频列表，可以用vector<vector<string>>存储
3. 结果统计：需要统计视频出现次数和排序，unordered_map<string, int>适合做频次统计

// 典型的数据结构定义示例 vector<vector<int>> friends; // 朋友关系图 vector<vector<string>> watchedVideos; // 每个用户观看的视频 unordered_map<string, int> videoCount; // 视频频次统计

2.2 核心算法流程

完整的算法流程可以分为三个主要步骤：

1. BFS遍历找到k层好友：

   • 使用队列实现标准BFS
   • 记录每个节点的访问层级
   • 当遇到层级等于k时收集用户ID

2. 统计视频观看频次：

   • 遍历所有k层好友
   • 对每个好友观看的视频进行计数
   • 使用哈希表记录每个视频的出现次数

3. 排序输出结果：

   • 首先按观看次数升序排序
   • 次数相同的按字母顺序排序
   • 可以使用自定义排序函数实现

2.3 边界条件处理

在实际编码中需要考虑以下边界情况：

• 起始用户ID无效的情况
• k=0时应该返回用户自己观看的视频
• 某些用户没有观看任何视频
• 朋友关系图为空的情况

3. 详细代码实现与解析

3.1 BFS实现查找k层好友

vector<int> getKLevelFriends(int n, vector<vector<int>>& friends, int id, int k) { vector<bool> visited(n, false); queue<pair<int, int>> q; // {user, level} vector<int> result; q.push({id, 0}); visited[id] = true; while (!q.empty()) { auto [user, level] = q.front(); q.pop(); if (level == k) { result.push_back(user); continue; // 不需要再处理更深层的朋友 } for (int friendId : friends[user]) { if (!visited[friendId]) { visited[friendId] = true; q.push({friendId, level + 1}); } } } return result; }

这段代码实现了标准的BFS遍历，特别注意：

1. 使用pair同时记录用户ID和当前层级
2. 当层级等于k时收集结果并跳过进一步处理
3. 使用visited数组避免重复访问

3.2 视频频次统计与排序

vector<string> getWatchedVideos(vector<int>& users, vector<vector<string>>& watchedVideos) { unordered_map<string, int> count; // 统计视频出现次数 for (int user : users) { for (string& video : watchedVideos[user]) { count[video]++; } } // 转换为vector便于排序 vector<pair<string, int>> videos(count.begin(), count.end()); // 自定义排序 auto cmp = [](const pair<string, int>& a, const pair<string, int>& b) { return a.second == b.second ? a.first < b.first : a.second < b.second; }; sort(videos.begin(), videos.end(), cmp); // 提取结果 vector<string> result; for (auto& [video, cnt] : videos) { result.push_back(video); } return result; }

这段代码的关键点：

1. 使用哈希表高效统计频次
2. 自定义排序函数实现题目要求的排序规则
3. 使用C++17的结构化绑定简化代码

3.3 完整解决方案

将上述两部分组合起来，得到完整解法：

class Solution { public: vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int k) { int n = friends.size(); vector<bool> visited(n, false); queue<pair<int, int>> q; vector<int> kLevelFriends; // BFS找k层好友 q.push({id, 0}); visited[id] = true; while (!q.empty()) { auto [user, level] = q.front(); q.pop(); if (level == k) { kLevelFriends.push_back(user); continue; } for (int friendId : friends[user]) { if (!visited[friendId]) { visited[friendId] = true; q.push({friendId, level + 1}); } } } // 统计视频频次 unordered_map<string, int> count; for (int user : kLevelFriends) { for (string& video : watchedVideos[user]) { count[video]++; } } // 排序 vector<pair<string, int>> videos(count.begin(), count.end()); auto cmp = [](const pair<string, int>& a, const pair<string, int>& b) { return a.second == b.second ? a.first < b.first : a.second < b.second; }; sort(videos.begin(), videos.end(), cmp); // 构造结果 vector<string> result; for (auto& [video, cnt] : videos) { result.push_back(video); } return result; } };

4. 复杂度分析与优化思路

4.1 时间复杂度分析

1. BFS部分：O(V + E)，其中V是用户数量，E是朋友关系数量
2. 视频统计部分：O(M)，M是所有k层好友观看的视频总数
3. 排序部分：O(N log N)，N是不同视频的数量

总体时间复杂度为O(V + E + M + N log N)，在LeetCode的约束条件下是完全可行的。

4.2 空间复杂度分析

1. 访问标记数组：O(V)
2. 队列：最坏情况O(V)
3. 哈希表：O(N)
4. 排序辅助数组：O(N)

总体空间复杂度为O(V + N)。

4.3 可能的优化方向

1. 双向BFS：当k值较大时，可以考虑从两端同时搜索
2. 预处理：如果需要多次查询，可以预处理所有用户之间的最短距离
3. 并行统计：对于大规模数据，可以并行统计不同好友的视频观看情况

5. 常见错误与调试技巧

5.1 常见错误类型

1. 层级计算错误：

   • 错误地将累计距离不超过k的朋友都包含进来
   • 解决方法：在BFS中严格判断level == k时才收集结果

2. 排序规则错误：

   • 只按频次或只按字母排序
   • 解决方法：自定义排序函数必须同时考虑两个条件

3. 重复计数：

   • 同一个用户被多次统计
   • 解决方法：确保BFS中使用visited数组

5.2 调试技巧

1. 打印中间结果：

   // 在BFS后打印找到的好友 cout << "K-level friends: "; for (int user : kLevelFriends) cout << user << " "; cout << endl;

2. 检查边界条件：

   • 特别测试k=0和k=1的情况
   • 测试起始用户没有朋友的情况

3. 小规模测试用例：

   /* 测试用例： 用户0的朋友：[1,2] 用户1的朋友：[0,3] 用户2的朋友：[0] 用户3的朋友：[1] 观看视频：[["A","B"], ["C"], ["B","C"], ["A"]] id=0, k=1 应该返回 ["A","B","C"] */

6. 相似题目与扩展思考

6.1 LeetCode相似题目推荐

1. 127. Word Ladder：同样使用BFS的最短路径问题
2. 133. Clone Graph：图的遍历与复制
3. 347. Top K Frequent Elements：频次统计与排序
4. 692. Top K Frequent Words：更接近本题的字符串频次排序

6.2 实际应用扩展

这个问题可以扩展到很多实际场景：

1. 社交网络推荐系统：基于好友关系推荐内容
2. 病毒传播分析：模拟信息在社交网络中的传播
3. 网络安全分析：识别特定距离内的关联节点

6.3 算法选择思考

为什么本题使用BFS而不是DFS？

• BFS天然适合查找最短路径/最小距离
• DFS可能会先深入某些路径，导致层级判断复杂
• BFS的队列结构便于按层级处理节点

7. 不同语言实现对比

7.1 Python实现特点

def watchedVideosByFriends(self, watchedVideos, friends, id, k): from collections import deque, defaultdict # BFS找k层好友 queue = deque([(id, 0)]) visited = {id} k_friends = [] while queue: user, level = queue.popleft() if level == k: k_friends.append(user) continue for friend in friends[user]: if friend not in visited: visited.add(friend) queue.append((friend, level + 1)) # 统计视频频次 count = defaultdict(int) for user in k_friends: for video in watchedVideos[user]: count[video] += 1 # 排序并返回 return [video for video, _ in sorted(count.items(), key=lambda x: (x[1], x[0]))]

Python实现注意点：

1. 使用collections.deque实现高效队列
2. defaultdict简化频次统计
3. 排序使用元组比较实现多条件排序

7.2 Java实现特点

public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, List<List<Integer>> friends, int id, int k) { // BFS找k层好友 Queue<int[]> queue = new LinkedList<>(); boolean[] visited = new boolean[friends.size()]; queue.offer(new int[]{id, 0}); visited[id] = true; List<Integer> kFriends = new ArrayList<>(); while (!queue.isEmpty()) { int[] curr = queue.poll(); if (curr[1] == k) { kFriends.add(curr[0]); continue; } for (int friend : friends.get(curr[0])) { if (!visited[friend]) { visited[friend] = true; queue.offer(new int[]{friend, curr[1] + 1}); } } } // 统计视频频次 Map<String, Integer> count = new HashMap<>(); for (int user : kFriends) { for (String video : watchedVideos.get(user)) { count.put(video, count.getOrDefault(video, 0) + 1); } } // 排序 List<Map.Entry<String, Integer>> list = new ArrayList<>(count.entrySet()); list.sort((a, b) -> { if (a.getValue().equals(b.getValue())) { return a.getKey().compareTo(b.getKey()); } return a.getValue() - b.getValue(); }); // 构造结果 List<String> result = new ArrayList<>(); for (Map.Entry<String, Integer> entry : list) { result.add(entry.getKey()); } return result; }

Java实现注意点：

1. 使用Queue接口和LinkedList实现队列
2. Map和getOrDefault简化频次统计
3. 自定义Comparator实现多条件排序

8. 实际工程中的考虑

在实际工程项目中，处理类似问题时还需要考虑：

1. 数据规模：当用户量很大时，需要考虑分布式处理
2. 实时性要求：是否需要实时计算，还是可以预处理
3. 数据更新频率：朋友关系和观看视频的更新频率如何
4. 内存限制：对于特别大的图，需要考虑内存友好的表示方法

一个可能的优化是使用邻接表压缩存储朋友关系，或者使用数据库存储朋友关系，通过SQL查询特定距离的好友。

对于视频频次统计，可以考虑使用概率数据结构如Count-Min Sketch来节省内存，特别是当视频种类非常多时。