获取你好友已观看的视频

标签: 广度优先搜索 图 数组 哈希表 排序

难度: Medium

有 n 个人，每个人都有一个  0 到 n-1 的唯一 id 。

给你数组 watchedVideos  和 friends ，其中 watchedVideos[i]  和 friends[i] 分别表示 id = i 的人观看过的视频列表和他的好友列表。

Level 1 的视频包含所有你好友观看过的视频，level 2 的视频包含所有你好友的好友观看过的视频，以此类推。一般的，Level 为 k 的视频包含所有从你出发，最短距离为 k 的好友观看过的视频。

给定你的 id  和一个 level 值，请你找出所有指定 level 的视频，并将它们按观看频率升序返回。如果有频率相同的视频，请将它们按字母顺序从小到大排列。

示例 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

Submission

运行时间: 50 ms

内存: 17.7 MB

from collections import defaultdict

class Solution:
    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
        n = len(friends)
        used = [False] * n
        q = collections.deque([id])
        used[id] = True
        for _ in range(level):
            span = len(q)
            for i in range(span):
                u = q.popleft()
                for v in friends[u]:
                    if not used[v]:
                        q.append(v)
                        used[v] = True
        dic = {}
        for i in q:
            for movie in watchedVideos[i]:
                dic[movie] = dic.get(movie, 0) + 1
        movie_cnt = [(dic[k], k) for k in dic.keys()]
        movie_cnt.sort()
        return [_[1] for _ in movie_cnt]

Explain

此算法使用广度优先搜索（BFS）来找到特定level的朋友，然后统计这些朋友所观看的视频的频率。首先，使用一个队列来实现BFS，从给定的id开始，标记已访问的节点以避免重复访问。连续进行BFS直到达到所需的level。在达到指定level后，从队列中收集所有的好友id，并统计他们观看的视频及其出现的频次。最后，将视频根据出现频率（升序）和字母顺序（升序）进行排序，并返回排序后的视频列表。

时间复杂度: O(n^2 + m log m)

空间复杂度: O(n + m)

from collections import defaultdict, deque

class Solution:
    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
        n = len(friends)
        used = [False] * n
        q = deque([id])
        used[id] = True
        for _ in range(level):
            span = len(q)
            for i in range(span):
                u = q.popleft()
                for v in friends[u]:
                    if not used[v]:
                        q.append(v)
                        used[v] = True
        dic = {}
        for i in q:
            for movie in watchedVideos[i]:
                dic[movie] = dic.get(movie, 0) + 1
        movie_cnt = [(dic[k], k) for k in dic.keys()]
        movie_cnt.sort()
        return [_[1] for _ in movie_cnt]

Explore

在广度优先搜索（BFS）中，为了避免重复访问已经搜索过的朋友，算法使用了一个布尔数组 `used`。该数组的索引对应于每个朋友的id，初始值全为False。当某个朋友的id第一次从队列中取出时，将对应的 `used[id]` 设置为True。在后续的搜索中，如果遇到已经被设置为True的 `used[v]`，则该朋友将不会再次被加入到队列中，从而防止了重复访问。

在统计视频观看频率时，使用字典（或哈希表）可以更高效地记录和查询每个视频及其出现次数。字典允许以视频名称为键，其观看次数为值，这样可以在常数时间内增加或获取视频的观看次数。使用列表或集合则不便于直接记录视频的观看次数，因为它们不支持以视频名为键进行快速检索和更新频率的操作。因此，字典是处理此类具有键值对关系的最佳数据结构。

如果某个用户没有任何好友，那么在执行BFS时，由于从该用户开始的队列将不会有任何其他好友id加入，队列中只包含该用户自己。因此，当队列进行到指定的level时（如果level大于0），队列将为空。此时，算法将直接返回一个空的视频列表，因为没有任何好友的视频数据可以收集和统计。

在BFS中使用span变量来控制队列的长度是为了确保每次循环只处理当前层的朋友。在算法开始每层的循环时，队列中包含的是上一层的所有朋友。通过记录这个长度（即span），我们可以确保在这一轮循环中只扩展这些朋友的朋友。这是因为在内部循环中，新发现的朋友被添加到队列的末尾，而span确保了循环只处理当前层的元素，不会处理到新加入的朋友，从而正确地逐层进行搜索。