获取你好友已观看的视频

难度:

标签:

题目描述

有 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

代码结果

运行时间: 50 ms, 内存: 17.7 MB

/* 
题目思路：
1. 使用BFS找到指定level的好友。
2. 统计这些好友观看的视频频率。
3. 根据频率和字母顺序对视频进行排序。
*/
import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, List<List<Integer>> friends, int id, int level) {
        int n = friends.size();
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(id);
        visited[id] = true;
        int currentLevel = 0;
        while (!queue.isEmpty() && currentLevel < level) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                for (int friend : friends.get(cur)) {
                    if (!visited[friend]) {
                        queue.offer(friend);
                        visited[friend] = true;
                    }
                }
            }
            currentLevel++;
        }
        Map<String, Long> videoCount = queue.stream()
            .flatMap(friend -> watchedVideos.get(friend).stream())
            .collect(Collectors.groupingBy(video -> video, Collectors.counting()));
        return videoCount.entrySet().stream()
            .sorted((a, b) -> a.getValue().equals(b.getValue()) ? a.getKey().compareTo(b.getKey()) : a.getValue().compareTo(b.getValue()))
            .map(Map.Entry::getKey)
            .collect(Collectors.toList());
    }
}

解释

方法:

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

时间复杂度:

O(n^2 + m log m)

空间复杂度:

O(n + m)

代码细节讲解

🦆

在广度优先搜索中，如何确保不会重复访问已经搜索过的朋友？

▷

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

🦆

在统计视频观看频率时，为什么选择使用字典而不是其他数据结构，如列表或集合？

▷

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

🦆

在算法中，如何处理如果某个用户没有任何好友的情况？

▷

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

🦆

为什么需要在for循环中使用span变量来控制队列的长度？

▷

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

获取你好友已观看的视频

题目描述

代码结果

解释

代码细节讲解

相关问题