Medium

题目描述

有 n 个人，每个人都有一个从 0 到 n-1 的唯一 id。给定数组 watchedVideos 和 friends，其中 watchedVideos[i] 和 friends[i] 分别包含 id = i 的人观看的视频列表和朋友列表。

第 1 级视频是所有你朋友观看的视频，第 2 级视频是所有你朋友的朋友观看的视频，依此类推。一般来说，第 k 级视频是所有与你的最短路径刚好等于 k 的人观看的视频。

给定你的 id 和视频的级别，返回按频率排序的视频列表（频率递增）。对于相同频率的视频，按字典序从小到大排序。

示例 1：

输入：watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1
输出：["B","C"]
解释：
你的 id = 0（图中绿色），你的朋友是（图中黄色）：
id = 1 的人 -> watchedVideos = ["C"] 
id = 2 的人 -> watchedVideos = ["B","C"] 
你朋友观看视频的频率：
B -> 1 
C -> 2

示例 2：

输入：watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 2
输出：["D"]
解释：
你的 id = 0（图中绿色），你朋友的朋友中只有 id = 3 的人（图中黄色）。

约束条件：

  • n == watchedVideos.length == friends.length
  • 2 <= n <= 100
  • 1 <= watchedVideos[i].length <= 100
  • 1 <= watchedVideos[i][j].length <= 8
  • 0 <= friends[i].length < n
  • 0 <= friends[i][j] < n
  • 0 <= id < n
  • 1 <= level < n
  • 如果 friends[i] 包含 j，那么 friends[j] 包含 i

解题思路

这道题需要在朋友关系图中找到指定层级的朋友，然后统计他们观看的视频频率。

核心思路：

  1. BFS 寻找指定层级的朋友：从给定的 id 开始，使用广度优先搜索找到距离恰好为 level 的所有朋友。需要用队列记录当前层级的人员，用集合记录已访问的人员避免重复。

  2. 统计视频频率：遍历找到的指定层级朋友，统计他们观看的所有视频及其出现频率。使用哈希表记录每个视频的观看次数。

  3. 排序输出：按照题目要求对视频进行排序：

    • 首先按频率从低到高排序
    • 频率相同时按字典序排序

算法步骤：

  • 初始化队列，将起始 id 加入队列，设置已访问集合
  • 进行 level 轮 BFS，每轮处理当前层级的所有人员，将他们的朋友加入下一层
  • 统计最终层级所有人员观看的视频频率
  • 将视频按频率和字典序排序后返回

这是一个典型的图论 + BFS 问题，时间复杂度主要由 BFS 遍历和最终排序决定。

代码实现

class Solution {
public:
    vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
        queue<int> q;
        unordered_set<int> visited;
        
        q.push(id);
        visited.insert(id);
        
        // BFS to find friends at the specified level
        for (int i = 0; i < level; i++) {
            int size = q.size();
            for (int j = 0; j < size; j++) {
                int curr = q.front();
                q.pop();
                
                for (int friend_id : friends[curr]) {
                    if (visited.find(friend_id) == visited.end()) {
                        visited.insert(friend_id);
                        q.push(friend_id);
                    }
                }
            }
        }
        
        // Count video frequencies
        unordered_map<string, int> videoCount;
        while (!q.empty()) {
            int friend_id = q.front();
            q.pop();
            
            for (const string& video : watchedVideos[friend_id]) {
                videoCount[video]++;
            }
        }
        
        // Sort by frequency then alphabetically
        vector<pair<int, string>> videos;
        for (auto& p : videoCount) {
            videos.push_back({p.second, p.first});
        }
        
        sort(videos.begin(), videos.end());
        
        vector<string> result;
        for (auto& p : videos) {
            result.push_back(p.second);
        }
        
        return result;
    }
};

class Solution:
    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
        from collections import deque, Counter
        
        queue = deque([id])
        visited = {id}
        
        # BFS to find friends at the specified level
        for _ in range(level):
            size = len(queue)
            for _ in range(size):
                curr = queue.popleft()
                
                for friend_id in friends[curr]:
                    if friend_id not in visited:
                        visited.add(friend_id)
                        queue.append(friend_id)
        
        # Count video frequencies
        video_count = Counter()
        for friend_id in queue:
            for video in watchedVideos[friend_id]:
                video_count[video] += 1
        
        # Sort by frequency then alphabetically
        videos = list(video_count.items())
        videos.sort(key=lambda x: (x[1], x[0]))
        
        return [video for video, _ in videos]

public class Solution {
    public IList<string> WatchedVideosByFriends(IList<IList<string>> watchedVideos, int[][] friends, int id, int level) {
        Queue<int> queue = new Queue<int>();
        HashSet<int> visited = new HashSet<int>();
        
        queue.Enqueue(id);
        visited.Add(id);
        
        // BFS to find friends at the specified level
        for (int i = 0; i < level; i++) {
            int size = queue.Count;
            for (int j = 0; j < size; j++) {
                int curr = queue.Dequeue();
                
                foreach (int friendId in friends[curr]) {
                    if (!visited.Contains(friendId)) {
                        visited.Add(friendId);
                        queue.Enqueue(friendId);
                    }
                }
            }
        }
        
        // Count video frequencies
        Dictionary<string, int> videoCount = new Dictionary<string, int>();
        while (queue.Count > 0) {
            int friendId = queue.Dequeue();
            
            foreach (string video in watchedVideos[friendId]) {
                if (videoCount.ContainsKey(video)) {
                    videoCount[video]++;
                } else {
                    videoCount[video] = 1;
                }
            }
        }
        
        // Sort by frequency then alphabetically
        var videos = videoCount.ToList();
        videos.Sort((x, y) => {
            if (x.Value != y.Value) {
                return x.Value.CompareTo(y.Value);
            }
            return x.Key.CompareTo(y.Key);
        });
        
        List<string> result = new List<string>();
        foreach (var kvp in videos) {
            result.Add(kvp.Key);
        }
        
        return result;
    }
}

var watchedVideosByFriends = function(watchedVideos, friends, id, level) {
    let queue = [id];
    let visited = new Set([id]);
    
    // BFS to find friends at the specified level
    for (let i = 0; i < level; i++) {
        let size = queue.length;
        let nextQueue = [];
        
        for (let j = 0; j < size; j++) {
            let curr = queue[j];
            
            for (let friendId of friends[curr]) {
                if (!visited.has(friendId)) {
                    visited.add(friendId);
                    nextQueue.push(friendId);
                }
            }
        }
        
        queue = nextQueue;
    }
    
    // Count video frequencies
    let videoCount = new Map();
    for (let friendId of queue) {
        for (let video of watchedVideos[friendId]) {
            videoCount.set(video, (videoCount.get(video) || 0) + 1);
        }
    }
    
    // Sort by frequency then alphabetically
    let videos = Array.from(videoCount.entries());
    videos.sort((a, b) => {
        if (a[1] !== b[1]) {
            return a[1] - b[1];
        }
        return a[0].localeCompare(b[0]);
    });
    
    return videos.map(entry => entry[0]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n + V log V)，其中 n 是人数，V 是视频总数。BFS 遍历需要 O(n)，统计和排序视频需要 O(V log V)
空间复杂度O(n + V)，队列和访问集合需要 O(n) 空间，视频计数哈希表需要 O(V) 空间