leetcode
leetcode 2101 ~ 2150
最流行的视频创作者

最流行的视频创作者

难度:

标签:

题目描述

代码结果

运行时间: 101 ms, 内存: 59.6 MB


/*
 * 思路:
 * 1. 使用流来处理输入数据。
 * 2. 使用Collectors.groupingBy收集创作者的数据,统计每个创作者的总播放量和每个创作者的所有视频信息。
 * 3. 使用Collectors.maxBy找到播放量最高的创作者。
 * 4. 对于每个播放量最高的创作者,找到他们播放量最高的视频的ID(如果有多个,选择字典序最小的一个)。
 * 5. 返回结果。
 */

import java.util.*;
import java.util.Map.Entry;
import java.util.stream.*;

public class Solution {
    public List<List<String>> mostPopularCreator(String[] creators, String[] ids, int[] views) {
        int n = creators.length;

        Map<String, List<Video>> creatorVideos = IntStream.range(0, n).mapToObj(i -> new Video(creators[i], ids[i], views[i]))
            .collect(Collectors.groupingBy(video -> video.creator));

        Map<String, Integer> creatorViews = creatorVideos.entrySet().stream()
            .collect(Collectors.toMap(Map.Entry::getKey, entry -> entry.getValue().stream().mapToInt(video -> video.view).sum()));

        int maxPopularity = creatorViews.values().stream().max(Integer::compareTo).orElse(0);

        return creatorViews.entrySet().stream()
            .filter(entry -> entry.getValue() == maxPopularity)
            .map(entry -> {
                String creator = entry.getKey();
                String maxViewId = creatorVideos.get(creator).stream()
                    .max(Comparator.comparingInt((Video v) -> v.view).thenComparing(v -> v.id)).get().id;
                return Arrays.asList(creator, maxViewId);
            })
            .collect(Collectors.toList());
    }

    static class Video {
        String creator;
        String id;
        int view;

        Video(String creator, String id, int view) {
            this.creator = creator;
            this.id = id;
            this.view = view;
        }
    }
}

解释

方法:

首先,该解法利用一个字典m来存储每个创作者(video creator)的总播放量、最大播放量和最大播放量对应的视频ID。遍历给定的数组,对于每个视频,更新其创作者在字典中的总播放量,并根据当前视频的播放量和ID更新创作者的最大播放量视频ID。如果当前视频的播放量大于记录的最大播放量,或者播放量相等但视频ID的字典序小于当前记录的ID,就更新记录。接着,我们找到字典中总播放量最大的值,然后从字典中提取出所有总播放量等于这个最大值的创作者和他们的最大播放量视频ID。这样就得到了流行度最高的创作者及其最流行视频的ID。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在处理多个最高播放量视频时,如何保证选择的视频ID是字典序最小的?
在更新创作者的最大播放量视频ID时,算法不仅比较当前视频的播放量与已记录的最大播放量,而且当播放量相同时,还会比较视频ID的字典序。如果当前视频的播放量大于已记录的最大播放量,或者播放量相同但当前视频ID的字典序小于已记录的视频ID,算法就会更新创作者的记录为当前视频的ID。这样的逻辑确保了如果存在多个相同播放量的视频,选取的是字典序最小的视频ID。
🦆
如果输入数组中存在相同的视频ID但不同播放量,这个算法如何处理这种情况?
算法的实现不直接处理可能出现的相同视频ID但播放量不同的情况。在理想的设计中,每个视频ID应当是唯一的;然而,如果确实发生了重复ID的情况,算法会将最后遍历到的该ID的视频的播放量视为准确值,并更新相关的创作者信息。这可能导致数据不一致,因为算法假设每个ID是唯一对应一个播放量。
🦆
为什么在更新字典时选择使用列表来存储创作者的总播放量、最大播放量和最大播放量的视频ID,而不使用其他数据结构如元组或字典?
使用列表来存储相关数据是为了便于更新记录中的值,例如总播放量和最大播放量的视频ID。列表允许我们直接修改其中的元素,这在不断更新数据时非常方便。相比之下,元组是不可变的,所以每次更新都需要创建一个新的元组,这可能导致额外的内存分配。虽然使用字典也可实现相同功能,并且可能增加代码的可读性,但列表在这种情况下提供了一种简单且效率较高的解决方案。
🦆
算法在遍历结束后直接使用最大总播放量来过滤创作者,这种方法是否可能漏掉某些创作者,尤其是在有多个创作者总播放量相同但不是最大值的情况下?
算法设计的目的是找出总播放量最高的创作者及其对应的最流行视频。因此,它只关注那些总播放量等于记录中最大值的创作者。如果有多个创作者的总播放量相同且为最大值,算法会正确地返回所有这些创作者及其最流行的视频ID。对于那些总播放量较高但不是最大的创作者,他们并不是本题目所要求的输出对象,因此这种设计并不会漏掉目标输出,但确实没有提供有关非最大总播放量创作者的信息。

相关问题