搜索题目：获取你好友已观看的视频

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题获取你好友已观看的视频出处1311. 获取你好友已观看的视频难度5 级题目描述要求有n \texttt{n}n个人每个人都有一个从0 \texttt{0}0到n − 1 \texttt{n} - \texttt{1}n−1的唯一编号。给定数组watchedVideos \texttt{watchedVideos}watchedVideos和friends \texttt{friends}friends其中watchedVideos[i] \texttt{watchedVideos[i]}watchedVideos[i]和friends[i] \texttt{friends[i]}friends[i]分别表示编号为i \texttt{i}i的人观看过的视频列表和他的好友列表。第1 \texttt{1}1层的视频包含所有你好友观看过的视频第2 \texttt{2}2层的视频包含所有你好友的好友观看过的视频以此类推。一般而言第k \texttt{k}k层的视频包含所有从你出发最短距离恰好为k \texttt{k}k的好友观看过的视频。给定你的编号id \texttt{id}id和视频的层数level \texttt{level}level将视频列表按观看频率升序返回。如果有频率相同的视频则将它们按字母顺序从小到大排列。示例示例 1输入watchedVideos [[A,B],[C],[B,C],[D]], friends [[1,2],[0,3],[0,3],[1,2]], id 0, level 1 \texttt{watchedVideos [[A,B],[C],[B,C],[D]], friends [[1,2],[0,3],[0,3],[1,2]], id 0, level 1}watchedVideos [[A,B],[C],[B,C],[D]], friends [[1,2],[0,3],[0,3],[1,2]], id 0, level 1输出[B,C] \texttt{[B,C]}[B,C]解释你的编号为0 \texttt{0}0绿色你的朋友包括黄色编号为1 → watchedVideos [C] \texttt{1} \rightarrow \texttt{watchedVideos [C]}1→watchedVideos [C]编号为2 → watchedVideos [B,C] \texttt{2} \rightarrow \texttt{watchedVideos [B,C]}2→watchedVideos [B,C]你朋友观看过视频的频率为B → 1 \texttt{B} \rightarrow \texttt{1}B→1C → 2 \texttt{C} \rightarrow \texttt{2}C→2示例 2输入watchedVideos [[A,B],[C],[B,C],[D]], friends [[1,2],[0,3],[0,3],[1,2]], id 0, level 2 \texttt{watchedVideos [[A,B],[C],[B,C],[D]], friends [[1,2],[0,3],[0,3],[1,2]], id 0, level 2}watchedVideos [[A,B],[C],[B,C],[D]], friends [[1,2],[0,3],[0,3],[1,2]], id 0, level 2输出[D] \texttt{[D]}[D]解释你的编号为0 \texttt{0}0绿色你朋友的朋友只有一个人他的编号为3 \texttt{3}3黄色。数据范围n watchedVideos.length friends.length \texttt{n} \texttt{watchedVideos.length} \texttt{friends.length}nwatchedVideos.lengthfriends.length2 ≤ n ≤ 100 \texttt{2} \le \texttt{n} \le \texttt{100}2≤n≤1001 ≤ watchedVideos[i].length ≤ 100 \texttt{1} \le \texttt{watchedVideos[i].length} \le \texttt{100}1≤watchedVideos[i].length≤1001 ≤ watchedVideos[i][j].length ≤ 8 \texttt{1} \le \texttt{watchedVideos[i][j].length} \le \texttt{8}1≤watchedVideos[i][j].length≤80 ≤ friends[i].length n \texttt{0} \le \texttt{friends[i].length} \texttt{n}0≤friends[i].lengthn0 ≤ friends[i][j] n \texttt{0} \le \texttt{friends[i][j]} \texttt{n}0≤friends[i][j]n0 ≤ id n \texttt{0} \le \texttt{id} \texttt{n}0≤idn1 ≤ level n \texttt{1} \le \texttt{level} \texttt{n}1≤leveln如果friends[i] \texttt{friends[i]}friends[i]包含j \texttt{j}j那么friends[j] \texttt{friends[j]}friends[j]包含i \texttt{i}i解法思路和算法为了获取第level \textit{level}level层的全部视频需要首先得到第level \textit{level}level层的全部好友然后获取这些好友观看的视频。得到第level \textit{level}level层的全部好友的做法是从编号id \textit{id}id开始广度优先搜索每一轮遍历同一层的全部好友经过level \textit{level}level轮遍历之后即可得到第level \textit{level}level层的好友。广度优先搜索需要记录每个编号是否被访问过初始时只有编号id \textit{id}id状态是已访问其余编号的状态都是未访问。初始时将编号id \textit{id}id入队列。每一轮遍历之前需要首先得到队列内的元素个数此时队列内的元素为同一层的全部好友编号然后访问这些编号并将与这些编号相邻且未访问的编号入队列。一轮遍历结束之后当前层的全部元素都已经出队列并被访问此时队列内的元素为下一层的全部好友编号下一轮遍历时即可访问下一层的全部好友编号。该做法可以确保每一轮遍历的元素为同一层的全部好友编号。经过level \textit{level}level轮遍历之后队列内的元素为第level \textit{level}level层的全部好友编号。得到第level \textit{level}level层的全部好友之后遍历每个好友并获得该好友观看的视频使用哈希表记录第level \textit{level}level层的全部视频的观看频率最后将视频按频率升序和字典序升序的顺序排序并返回。代码classSolution{publicListStringwatchedVideosByFriends(ListListStringwatchedVideos,int[][]friends,intid,intlevel){intnwatchedVideos.size();boolean[]visitednewboolean[n];visited[id]true;QueueIntegerqueuenewArrayDequeInteger();queue.offer(id);while(!queue.isEmpty()level0){level--;intsizequeue.size();for(inti0;isize;i){intcurrqueue.poll();int[]currFriendsfriends[curr];for(intfriend:currFriends){if(!visited[friend]){visited[friend]true;queue.offer(friend);}}}}MapString,IntegercountsnewHashMapString,Integer();while(!queue.isEmpty()){intcurrqueue.poll();ListStringcurrVideoswatchedVideos.get(curr);for(Stringvideo:currVideos){counts.put(video,counts.getOrDefault(video,0)1);}}ListStringvideosByFriendsnewArrayListString(counts.keySet());Collections.sort(videosByFriends,(a,b)-{intcount1counts.get(a),count2counts.get(b);if(count1!count2){returncount1-count2;}else{returna.compareTo(b);}});returnvideosByFriends;}}复杂度分析时间复杂度O ( n m v log ⁡ v ) O(n m v \log v)O(nmvlogv)其中n nn是人数m mm是好友关系数v vv是电影数。广度优先搜索的时间复杂度是O ( n m ) O(n m)O(nm)计算电影的观看频率需要O ( v ) O(v)O(v)的时间排序需要O ( v log ⁡ v ) O(v \log v)O(vlogv)的时间因此时间复杂度是O ( n m v log ⁡ v ) O(n m v \log v)O(nmvlogv)。这里将字符串的长度视为常数。空间复杂度O ( n v ) O(n v)O(nv)其中n nn是人数v vv是电影数。队列需要O ( n ) O(n)O(n)的空间哈希表需要O ( n v ) O(n v)O(nv)的空间排序需要O ( v ) O(v)O(v)的空间因此空间复杂度是O ( n v ) O(n v)O(nv)。这里将字符串的长度视为常数。