通过投票对团队排名

难度: Medium

现在有一个特殊的排名系统，依据参赛团队在投票人心中的次序进行排名，每个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。

排名规则如下：

参赛团队的排名次序依照其所获「排位第一」的票的多少决定。如果存在多个团队并列的情况，将继续考虑其「排位第二」的票的数量。以此类推，直到不再存在并列的情况。
如果在考虑完所有投票情况后仍然出现并列现象，则根据团队字母的字母顺序进行排名。

给你一个字符串数组 votes 代表全体投票者给出的排位情况，请你根据上述排名规则对所有参赛团队进行排名。

请你返回能表示按排名系统 排序后 的所有团队排名的字符串。

示例 1：

输入：votes = ["ABC","ACB","ABC","ACB","ACB"]
输出："ACB"
解释：A 队获得五票「排位第一」，没有其他队获得「排位第一」，所以 A 队排名第一。
B 队获得两票「排位第二」，三票「排位第三」。
C 队获得三票「排位第二」，两票「排位第三」。
由于 C 队「排位第二」的票数较多，所以 C 队排第二，B 队排第三。

示例 2：

输入：votes = ["WXYZ","XYZW"]
输出："XWYZ"
解释：X 队在并列僵局打破后成为排名第一的团队。X 队和 W 队的「排位第一」票数一样，但是 X 队有一票「排位第二」，而 W 没有获得「排位第二」。

示例 3：

输入：votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
输出："ZMNAGUEDSJYLBOPHRQICWFXTVK"
解释：只有一个投票者，所以排名完全按照他的意愿。

示例 4：

输入：votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]
输出："ABC"
解释： 
A 队获得两票「排位第一」，两票「排位第二」，两票「排位第三」。
B 队获得两票「排位第一」，两票「排位第二」，两票「排位第三」。
C 队获得两票「排位第一」，两票「排位第二」，两票「排位第三」。
完全并列，所以我们需要按照字母升序排名。

示例 5：

输入：votes = ["M","M","M","M"]
输出："M"
解释：只有 M 队参赛，所以它排名第一。

提示：

1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= i, j < votes.length
votes[i][j] 是英文大写字母
votes[i] 中的所有字母都是唯一的
votes[0] 中出现的所有字母 同样也 出现在 votes[j] 中，其中 1 <= j < votes.length

Submission

运行时间: 35 ms

内存: 16.3 MB

from typing import List
from collections import defaultdict

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        teamNum = len(votes[0])
    # 给defaultdict()传递函数名或者类名，将value默认初始化为对应的返回值
        team2RankList = defaultdict(lambda: [0] * teamNum)

        for vote in votes:
            for rank, team in enumerate(vote):

                team2RankList[team][rank] += 1

    # 按照每个团队在各个名次的票数进行排序，再按照团队字母顺序排序
    # 先按照x[1]列表中依次从大到小进行排序，如果x[1]中所有数字都相同，则按照x[0]进行从小到大进行排序(只支持数字排序，不支持字符串)
    # 排序前：[('A', [5, 0, 0]), ('B', [0, 2, 3]), ('C', [0, 3, 2])]
    # 排序后：[('A', [5, 0, 0]), ('C', [0, 3, 2]), ('B', [0, 2, 3])]
        tupleList = sorted(team2RankList.items(), key=lambda x: (x[1], -ord(x[0])), reverse=True)
        return ''.join([x[0] for x in tupleList])

Explain

该题解的主要思路是通过构建一个字典来记录每个团队在各个排位上的得票数。首先，为每个团队创建一个列表，列表的长度等于团队数，用于记录该团队在每个排位上的票数。然后，遍历每个投票，更新相应团队的排位票数。最后，通过自定义排序函数，先根据团队的票数列表（从高到低）进行排序，如果票数列表相同，则根据团队的名称（字母顺序）进行排序。排序后，提取排序后的团队名称，组合成最终的字符串结果。

时间复杂度: O(n*m + m log m)

空间复杂度: O(m^2)

from typing import List
from collections import defaultdict

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        teamNum = len(votes[0])
        team2RankList = defaultdict(lambda: [0] * teamNum)

        for vote in votes:
            for rank, team in enumerate(vote):
                team2RankList[team][rank] += 1

        tupleList = sorted(team2RankList.items(), key=lambda x: (x[1], -ord(x[0])), reverse=True)
        return ''.join([x[0] for x in tupleList]) # 将排序后的团队名称拼接成字符串返回

Explore

在排序函数中，使用`-ord(x[0])`作为排序的一部分主要是用来处理当团队的票数列表完全相同的情况。在Python中，列表排序默认是升序排序，即数值越小越靠前。通过使用`-ord(x[0])`（即团队名称的ASCII值的负值），我们可以确保如果票数列表相同，那么团队名称按字母顺序逆序排列。由于最终排序是按照票数列表降序进行的，这种逆序的结果实际上使得相同票数的团队按字母顺序正序排列，符合题目要求。

在这个题解中，每个团队的票数列表长度是一致的，因为它直接对应于每个投票中的团队位置数量，即团队数。因此，每个团队的票数列表都有相同的长度，这保证了排序的公平性和准确性。如果票数列表长度不一致，可能会影响排序结果的准确性，因为列表长度不同可能导致排序机制无法正确比较。但在本题中，这种情况不存在，所以可以直接使用票数列表作为排序关键字。

在Python中，使用`defaultdict`可以自动为字典尚未有映射值的键提供一个默认值。在这个题解中，`defaultdict`用于创建一个默认的票数列表（每个元素初始化为0），这样在更新票数时，即使某些团队之前没有记录，也可以直接更新其票数而无需先检查键是否存在。这简化了代码逻辑，增加了代码的可读性和效率。相比之下，如果使用普通字典，每次更新之前都需要手动检查并可能初始化键，这会使代码更加冗长和容易出错。

如果所有投票都是相同的排名，那么每个团队的票数列表将完全相同（每个位置的票数都相等）。在这种情况下，排序的主要依据（票数列表）无法区分团队的顺序，因此排序将依靠次要条件，即团队名称的字母顺序。由于代码中使用了`-ord(x[0])`作为次要排序标准，并且最终排序是降序，实际上将使团队按字母顺序升序排列。因此，即便所有投票相同，这种方法仍然能正确地根据字母顺序返回团队排序，符合预期。