最流行的视频创作者

标签: 数组 哈希表 字符串 排序 堆（优先队列）

难度: Medium

给你两个字符串数组 creators 和 ids ，和一个整数数组 views ，所有数组的长度都是 n 。平台上第 i 个视频者是 creator[i] ，视频分配的 id 是 ids[i] ，且播放量为 views[i] 。

视频创作者的 流行度 是该创作者的 所有 视频的播放量的 总和 。请找出流行度 最高 创作者以及该创作者播放量 最大 的视频的 id 。

  • 如果存在多个创作者流行度都最高，则需要找出所有符合条件的创作者。
  • 如果某个创作者存在多个播放量最高的视频，则只需要找出字典序最小的 id 。

返回一个二维字符串数组 answer ，其中 answer[i] = [creatori, idi] 表示 creatori 的流行度 最高 且其最流行的视频 id 是 idi ，可以按任何顺序返回该结果。

示例 1：

输入：creators = ["alice","bob","alice","chris"], ids = ["one","two","three","four"], views = [5,10,5,4]
输出：[["alice","one"],["bob","two"]]
解释：
alice 的流行度是 5 + 5 = 10 。
bob 的流行度是 10 。
chris 的流行度是 4 。
alice 和 bob 是流行度最高的创作者。
bob 播放量最高的视频 id 为 "two" 。
alice 播放量最高的视频 id 是 "one" 和 "three" 。由于 "one" 的字典序比 "three" 更小，所以结果中返回的 id 是 "one" 。

示例 2：

输入：creators = ["alice","alice","alice"], ids = ["a","b","c"], views = [1,2,2]
输出：[["alice","b"]]
解释：
id 为 "b" 和 "c" 的视频都满足播放量最高的条件。
由于 "b" 的字典序比 "c" 更小，所以结果中返回的 id 是 "b" 。

提示：

  • n == creators.length == ids.length == views.length
  • 1 <= n <= 105
  • 1 <= creators[i].length, ids[i].length <= 5
  • creators[i] 和 ids[i] 仅由小写英文字母组成
  • 0 <= views[i] <= 105

Submission

运行时间: 101 ms

内存: 59.6 MB

class Solution:
    def mostPopularCreator(self, creators: List[str], ids: List[str], views: List[int]) -> List[List[str]]:
        m,max_view_sum={},0
        for name,id,view in zip(creators,ids,views):
            if name in m:
                t=m[name]
                t[0]+=view
                if view>t[1] or view==t[1] and id<t[2]:
                    t[1],t[2]=view,id
            else:
                m[name]=[view,view,id]
            max_view_sum=max(max_view_sum,m[name][0])
        return [[name,id] for name,(view_sum,_,id) in m.items() if view_sum==max_view_sum]

Explain

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

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def mostPopularCreator(self, creators: List[str], ids: List[str], views: List[int]) -> List[List[str]]:
        m,max_view_sum={},0 # m为字典，记录每个创作者的总播放量和最大播放量视频的信息
        for name,id,view in zip(creators,ids,views): # 遍历输入的视频信息
            if name in m: # 如果创作者已经在字典中
                t=m[name]
                t[0]+=view # 更新总播放量
                if view>t[1] or view==t[1] and id<t[2]: # 如果当前视频播放量更高，或播放量相同但ID字典序更小
                    t[1],t[2]=view,id # 更新最大播放量和对应的视频ID
            else:
                m[name]=[view,view,id] # 初始化创作者信息
            max_view_sum=max(max_view_sum,m[name][0]) # 更新最大的总播放量
        return [[name,id] for name,(view_sum,_,id) in m.items() if view_sum==max_view_sum] # 返回所有最大总播放量的创作者和其最大播放量视频的ID

Explore

在更新创作者的最大播放量视频ID时，算法不仅比较当前视频的播放量与已记录的最大播放量，而且当播放量相同时，还会比较视频ID的字典序。如果当前视频的播放量大于已记录的最大播放量，或者播放量相同但当前视频ID的字典序小于已记录的视频ID，算法就会更新创作者的记录为当前视频的ID。这样的逻辑确保了如果存在多个相同播放量的视频，选取的是字典序最小的视频ID。

算法的实现不直接处理可能出现的相同视频ID但播放量不同的情况。在理想的设计中，每个视频ID应当是唯一的；然而，如果确实发生了重复ID的情况，算法会将最后遍历到的该ID的视频的播放量视为准确值，并更新相关的创作者信息。这可能导致数据不一致，因为算法假设每个ID是唯一对应一个播放量。

使用列表来存储相关数据是为了便于更新记录中的值，例如总播放量和最大播放量的视频ID。列表允许我们直接修改其中的元素，这在不断更新数据时非常方便。相比之下，元组是不可变的，所以每次更新都需要创建一个新的元组，这可能导致额外的内存分配。虽然使用字典也可实现相同功能，并且可能增加代码的可读性，但列表在这种情况下提供了一种简单且效率较高的解决方案。

算法设计的目的是找出总播放量最高的创作者及其对应的最流行视频。因此，它只关注那些总播放量等于记录中最大值的创作者。如果有多个创作者的总播放量相同且为最大值，算法会正确地返回所有这些创作者及其最流行的视频ID。对于那些总播放量较高但不是最大的创作者，他们并不是本题目所要求的输出对象，因此这种设计并不会漏掉目标输出，但确实没有提供有关非最大总播放量创作者的信息。