通过投票对团队排名
难度:
标签:
题目描述
代码结果
运行时间: 35 ms, 内存: 16.3 MB
/*
* Problem Approach (Java Stream):
* 1. Similar to the above approach, we will use a map to store each team's vote count for each rank.
* 2. We will then use Java Streams to sort the teams based on the ranking rules.
* 3. Finally, we concatenate the sorted teams into a string and return it.
*/
import java.util.*;
import java.util.stream.Collectors;
public class RankTeamsStream {
public String rankTeams(String[] votes) {
int teamCount = votes[0].length();
Map<Character, int[]> voteMap = new HashMap<>();
for (char team : votes[0].toCharArray()) {
voteMap.put(team, new int[teamCount]);
}
for (String vote : votes) {
for (int i = 0; i < vote.length(); i++) {
voteMap.get(vote.charAt(i))[i]++;
}
}
return voteMap.entrySet().stream()
.sorted((entry1, entry2) -> {
for (int i = 0; i < teamCount; i++) {
if (entry1.getValue()[i] != entry2.getValue()[i]) {
return entry2.getValue()[i] - entry1.getValue()[i];
}
}
return entry1.getKey() - entry2.getKey();
})
.map(Map.Entry::getKey)
.map(String::valueOf)
.collect(Collectors.joining());
}
}
解释
方法:
该题解的主要思路是通过构建一个字典来记录每个团队在各个排位上的得票数。首先,为每个团队创建一个列表,列表的长度等于团队数,用于记录该团队在每个排位上的票数。然后,遍历每个投票,更新相应团队的排位票数。最后,通过自定义排序函数,先根据团队的票数列表(从高到低)进行排序,如果票数列表相同,则根据团队的名称(字母顺序)进行排序。排序后,提取排序后的团队名称,组合成最终的字符串结果。
时间复杂度:
O(n*m + m log m)
空间复杂度:
O(m^2)
代码细节讲解
🦆
在自定义排序函数中,为什么要使用`-ord(x[0])`作为排序的一部分?这种负值是如何影响排序结果的?
▷🦆
排序过程中,为什么可以直接将票数列表作为排序的关键字,不同长度的票数列表是否会影响排序的准确性?
▷🦆
代码中提到`team2RankList`采用的是defaultdict来初始化每个团队的票数列表,defaultdict相比普通字典有什么优势?
▷🦆
给定的解法中,如果所有投票都是相同的排名,排序函数是否还能正确地返回预期的团队排序?
▷