侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【哈希表】最流行的视频创作者【力扣第 317 场周赛】

GabrielxD
2022-10-30 / 0 评论 / 0 点赞 / 13 阅读 / 922 字 / 正在检测是否收录...

题目

6221. 最流行的视频创作者


给你两个字符串数组 creatorsids ,和一个整数数组 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 <= 10^5
  • 1 <= creators[i].length, ids[i].length <= 5
  • creators[i]ids[i] 仅由小写英文字母组成
  • 0 <= views[i] <= 10^5

解题

方法一:哈希表

思路

维护最高的累计播放量(maxTotalView)。

哈希表统计:

  • mp1:累计播放量对应的创作者(注意值要使用集合防止出现重复)。
  • mp2:创作者对应的累计播放量(辅助计算累计播放量)。
  • mp3:创作者对应的播放量最高的视频的索引(i)(有多个播放量最高的视频时取其 id 字典序最小的)。

然后从 mp1 找到所有累计播放量为最高累计播放量的创作者们,再从 mp3 中找到创作者对应符合要求的视频 id 加入结果集合中。

代码

class Solution {
    public List<List<String>> mostPopularCreator(String[] creators, String[] ids, int[] views) {
        int n = creators.length;
        int maxTotalView = 0;
        Map<Integer, Set<String>> mp1 = new HashMap<>();
        Map<String, Integer> mp2 = new HashMap<>(), mp3 = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            String c = creators[i];
            String id = ids[i];
            int v = views[i];
            int totalView = mp2.getOrDefault(c, 0) + v;
            if (totalView >= maxTotalView) {
                maxTotalView = totalView;
                mp1.putIfAbsent(totalView, new HashSet<>());
                mp1.get(totalView).add(c);
            }
            mp2.put(c, totalView);
            if (mp3.containsKey(c)) {
                int mvId = mp3.get(c);
                int maxView = views[mvId];
                if (v > maxView || (v == maxView && ids[i].compareTo(ids[mvId]) < 0)) mp3.put(c, i);
            } else mp3.put(c, i);
        }
        List<List<String>> ans = new ArrayList<>();
        for (String c : mp1.get(maxTotalView)) {
            String id = ids[mp3.get(c)];
            List<String> tmp = new ArrayList<>();
            tmp.add(c);
            tmp.add(id);
            ans.add(tmp);
        }
        return ans;
    }
}
0

评论区