leetcode
leetcode 1251 ~ 1300
通过投票对团队排名

通过投票对团队排名

难度:

标签:

题目描述

代码结果

运行时间: 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])`作为排序的一部分?这种负值是如何影响排序结果的?
在排序函数中,使用`-ord(x[0])`作为排序的一部分主要是用来处理当团队的票数列表完全相同的情况。在Python中,列表排序默认是升序排序,即数值越小越靠前。通过使用`-ord(x[0])`(即团队名称的ASCII值的负值),我们可以确保如果票数列表相同,那么团队名称按字母顺序逆序排列。由于最终排序是按照票数列表降序进行的,这种逆序的结果实际上使得相同票数的团队按字母顺序正序排列,符合题目要求。
🦆
排序过程中,为什么可以直接将票数列表作为排序的关键字,不同长度的票数列表是否会影响排序的准确性?
在这个题解中,每个团队的票数列表长度是一致的,因为它直接对应于每个投票中的团队位置数量,即团队数。因此,每个团队的票数列表都有相同的长度,这保证了排序的公平性和准确性。如果票数列表长度不一致,可能会影响排序结果的准确性,因为列表长度不同可能导致排序机制无法正确比较。但在本题中,这种情况不存在,所以可以直接使用票数列表作为排序关键字。
🦆
代码中提到`team2RankList`采用的是defaultdict来初始化每个团队的票数列表,defaultdict相比普通字典有什么优势?
在Python中,使用`defaultdict`可以自动为字典尚未有映射值的键提供一个默认值。在这个题解中,`defaultdict`用于创建一个默认的票数列表(每个元素初始化为0),这样在更新票数时,即使某些团队之前没有记录,也可以直接更新其票数而无需先检查键是否存在。这简化了代码逻辑,增加了代码的可读性和效率。相比之下,如果使用普通字典,每次更新之前都需要手动检查并可能初始化键,这会使代码更加冗长和容易出错。
🦆
给定的解法中,如果所有投票都是相同的排名,排序函数是否还能正确地返回预期的团队排序?
如果所有投票都是相同的排名,那么每个团队的票数列表将完全相同(每个位置的票数都相等)。在这种情况下,排序的主要依据(票数列表)无法区分团队的顺序,因此排序将依靠次要条件,即团队名称的字母顺序。由于代码中使用了`-ord(x[0])`作为次要排序标准,并且最终排序是降序,实际上将使团队按字母顺序升序排列。因此,即便所有投票相同,这种方法仍然能正确地根据字母顺序返回团队排序,符合预期。

相关问题