Medium

题目描述

给你两个字符串数组 creators 和 ids，以及一个整数数组 views，三个数组的长度都是 n。平台上第 i 个视频是由 creators[i] 创作的，视频的 id 是 ids[i]，并且有 views[i] 的观看次数。

一个创作者的流行度是其所有视频观看次数的总和。找出流行度最高的创作者以及该创作者观看次数最多的视频的 id。

  • 如果有多个创作者的流行度都是最高的，返回所有这些创作者。
  • 如果一个创作者有多个观看次数最多的视频，返回字典序最小的视频 id。

注意： 不同的视频可能有相同的 id，也就是说 id 不能唯一标识一个视频。例如，两个有相同 ID 的视频被认为是具有各自观看次数的不同视频。

返回一个二维字符串数组 answer，其中 answer[i] = [creatorsi, idi] 表示 creatorsi 的流行度最高，idi 是该创作者最受欢迎视频的 id。答案可以按任何顺序返回。

示例 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，观看次数最多的视频是 "two"。
对于 alice，观看次数最多的视频是 "one" 和 "three"。由于 "one" 在字典序上比 "three" 小，所以答案中包含 "one"。

示例 2:

输入：creators = ["alice","alice","alice"], ids = ["a","b","c"], views = [1,2,2]
输出：[["alice","b"]]
解释：
id 为 "b" 和 "c" 的视频观看次数最多。
由于 "b" 在字典序上比 "c" 小，所以答案中包含 "b"。

约束条件：

  • n == creators.length == ids.length == views.length
  • 1 <= n <= 10^5
  • 1 <= creators[i].length, ids[i].length <= 5
  • creators[i] 和 ids[i] 只包含小写英文字母
  • 0 <= views[i] <= 10^5

解题思路

这道题需要分两个步骤解决：

  1. 统计每个创作者的总流行度：遍历所有视频，用哈希表累加每个创作者的观看次数总和。

  2. 找出每个创作者观看次数最多的视频：对于每个创作者，需要记录其观看次数最高的视频ID。如果有多个视频观看次数相同且都是最高的，选择字典序最小的ID。

具体实现思路：

  • 使用两个哈希表：一个记录创作者的总观看次数，另一个记录创作者及其最受欢迎的视频信息
  • 遍历数组时，更新创作者的总观看次数，同时维护该创作者观看次数最多的视频ID
  • 在更新最受欢迎视频时，需要考虑观看次数相等的情况下选择字典序更小的ID
  • 找出最高的流行度，然后收集所有达到这个流行度的创作者及其对应的视频ID

时间复杂度分析： 需要遍历一次数组统计信息，然后遍历创作者找出最受欢迎的，整体为O(n)。 空间复杂度分析： 使用哈希表存储创作者信息，最坏情况下所有创作者都不同，为O(n)。

代码实现

class Solution {
public:
    vector<vector<string>> mostPopularCreator(vector<string>& creators, vector<string>& ids, vector<int>& views) {
        unordered_map<string, long long> totalViews;
        unordered_map<string, pair<int, string>> bestVideo;
        
        int n = creators.size();
        for (int i = 0; i < n; i++) {
            string creator = creators[i];
            string id = ids[i];
            int view = views[i];
            
            totalViews[creator] += view;
            
            if (bestVideo.find(creator) == bestVideo.end() || 
                view > bestVideo[creator].first || 
                (view == bestVideo[creator].first && id < bestVideo[creator].second)) {
                bestVideo[creator] = {view, id};
            }
        }
        
        long long maxViews = 0;
        for (auto& p : totalViews) {
            maxViews = max(maxViews, p.second);
        }
        
        vector<vector<string>> result;
        for (auto& p : totalViews) {
            if (p.second == maxViews) {
                result.push_back({p.first, bestVideo[p.first].second});
            }
        }
        
        return result;
    }
};

class Solution:
    def mostPopularCreator(self, creators: List[str], ids: List[str], views: List[int]) -> List[List[str]]:
        total_views = {}
        best_video = {}
        
        for creator, video_id, view in zip(creators, ids, views):
            total_views[creator] = total_views.get(creator, 0) + view
            
            if (creator not in best_video or 
                view > best_video[creator][0] or 
                (view == best_video[creator][0] and video_id < best_video[creator][1])):
                best_video[creator] = (view, video_id)
        
        max_views = max(total_views.values())
        
        result = []
        for creator, views_sum in total_views.items():
            if views_sum == max_views:
                result.append([creator, best_video[creator][1]])
        
        return result

public class Solution {
    public IList<IList<string>> MostPopularCreator(string[] creators, string[] ids, int[] views) {
        var totalViews = new Dictionary<string, long>();
        var bestVideo = new Dictionary<string, (int views, string id)>();
        
        int n = creators.Length;
        for (int i = 0; i < n; i++) {
            string creator = creators[i];
            string id = ids[i];
            int view = views[i];
            
            totalViews[creator] = totalViews.GetValueOrDefault(creator, 0) + view;
            
            if (!bestVideo.ContainsKey(creator) || 
                view > bestVideo[creator].views || 
                (view == bestVideo[creator].views && string.Compare(id, bestVideo[creator].id) < 0)) {
                bestVideo[creator] = (view, id);
            }
        }
        
        long maxViews = totalViews.Values.Max();
        
        var result = new List<IList<string>>();
        foreach (var kvp in totalViews) {
            if (kvp.Value == maxViews) {
                result.Add(new List<string> { kvp.Key, bestVideo[kvp.Key].id });
            }
        }
        
        return result;
    }
}

/**
 * @param {string[]} creators
 * @param {string[]} ids
 * @param {number[]} views
 * @return {string[][]}
 */
var mostPopularCreator = function(creators, ids, views) {
    const creatorStats = new Map();
    
    for (let i = 0; i < creators.length; i++) {
        const creator = creators[i];
        const id = ids[i];
        const view = views[i];
        
        if (!creatorStats.has(creator)) {
            creatorStats.set(creator, {
                totalViews: 0,
                maxViews: -1,
                mostPopularId: ""
            });
        }
        
        const stats = creatorStats.get(creator);
        stats.totalViews += view;
        
        if (view > stats.maxViews || (view === stats.maxViews && id < stats.mostPopularId)) {
            stats.maxViews = view;
            stats.mostPopularId = id;
        }
    }
    
    let maxPopularity = -1;
    for (const stats of creatorStats.values()) {
        maxPopularity = Math.max(maxPopularity, stats.totalViews);
    }
    
    const result = [];
    for (const [creator, stats] of creatorStats.entries()) {
        if (stats.totalViews === maxPopularity) {
            result.push([creator, stats.mostPopularId]);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 需要遍历一次所有视频数据，然后遍历所有创作者
空间复杂度O(n) - 在最坏情况下，所有创作者都不同，需要存储n个创作者的信息

相关题目