给你两个字符串数组 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
方法一:哈希表
我们用哈希表 cnt
统计每个创作者的视频播放量总和,用哈希表 d
和 x
记录每个创作者的最大播放量和对应的视频 id
。
然后遍历哈希表 cnt
,找到最大视频播放量总和的创作者,将其对应的视频 id
加入答案数组 ans
中。
时间复杂度
class Solution:
def mostPopularCreator(self, creators: List[str], ids: List[str], views: List[int]) -> List[List[str]]:
cnt = defaultdict(int)
d = {}
x = {}
for c, i, v in zip(creators, ids, views):
cnt[c] += v
if c not in d or d[c] < v or (d[c] == v and x[c] > i):
d[c], x[c] = v, i
ans = []
pre = -1
for a, b in cnt.items():
if b > pre:
ans = [[a, x[a]]]
pre = b
elif b == pre:
ans.append([a, x[a]])
return ans
class Solution {
public List<List<String>> mostPopularCreator(String[] creators, String[] ids, int[] views) {
Map<String, Integer> cnt = new HashMap<>();
Map<String, Integer> d = new HashMap<>();
Map<String, String> x = new HashMap<>();
int n = ids.length;
for (int k = 0; k < n; ++k) {
var c = creators[k];
var i = ids[k];
int v = views[k];
cnt.put(c, cnt.getOrDefault(c, 0) + v);
if (!d.containsKey(c) || d.get(c) < v || (d.get(c) == v && x.get(c).compareTo(i) > 0)) {
d.put(c, v);
x.put(c, i);
}
}
List<List<String>> ans = new ArrayList<>();
int pre = -1;
for (var e : cnt.entrySet()) {
String a = e.getKey();
int b = e.getValue();
if (b > pre) {
ans.clear();
ans.add(Arrays.asList(a, x.get(a)));
pre = b;
} else if (b == pre) {
ans.add(Arrays.asList(a, x.get(a)));
}
}
return ans;
}
}
class Solution {
public:
vector<vector<string>> mostPopularCreator(vector<string>& creators, vector<string>& ids, vector<int>& views) {
unordered_map<string, long> cnt;
unordered_map<string, int> d;
unordered_map<string, string> x;
int n = ids.size();
for (int k = 0; k < n; ++k) {
auto c = creators[k];
auto i = ids[k];
int v = views[k];
cnt[c] += v;
if (!d.count(c) || d[c] < v || (d[c] == v && x[c] > i)) {
d[c] = v;
x[c] = i;
}
}
long pre = -1;
vector<vector<string>> ans;
for (auto& [a, b] : cnt) {
if (b > pre) {
ans.clear();
ans.push_back({a, x[a]});
pre = b;
} else if (b == pre) {
ans.push_back({a, x[a]});
}
}
return ans;
}
};
func mostPopularCreator(creators []string, ids []string, views []int) (ans [][]string) {
cnt := map[string]int{}
d := map[string]int{}
x := map[string]string{}
for k, c := range creators {
i, v := ids[k], views[k]
cnt[c] += v
if t, ok := d[c]; !ok || t < v || (t == v && x[c] > i) {
d[c] = v
x[c] = i
}
}
pre := -1
for a, b := range cnt {
if b > pre {
ans = [][]string{[]string{a, x[a]}}
pre = b
} else if b == pre {
ans = append(ans, []string{a, x[a]})
}
}
return ans
}