1366-通过投票对团队排名

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

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

排名规则如下：

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

给你一个字符串数组 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

方法一：排序

设参与排名的人数为 n（即数组 votes 中任一字符串的长度），我们可以用一个哈希映射（HashMap）存储每一个人的排名情况。对于哈希映射中的每个键值对，键为一个在数组 votes 中出现的大写英文字母，表示一个参与排名的人；值为一个长度为 n 的数组 rank，表示这个人的排名情况，其中 rank}[i] 表示这个人排名为 i 的次数。

我们遍历数组 votes 中的每一个字符串并进行统计，就可以得到上述存储了每一个人排名情况的哈希映射。随后我们将这些键值对取出，并放入数组中进行排序。记每一个键值对为 (\textit{vid}, \textit{rank})，根据题目要求，我们需要以 rank 为第一关键字进行降序排序。在大部分语言中，我们是可以对变长的数组（例如 C++ 中的 vector，Python 中的 list）直接进行比较排序的，比较的方式是从首部的元素开始，依次比较两个数组同一位置的元素的大小，若相等则继续比较下一位置，直至数组的尾部（此时长度较长的数组较大，若长度相同，则这两个数组同样大）。因此第一关键字可以直接进行比较。在 rank 相等的情况下，我们需要以 vid 为第二关键字进行升序排序。在 C++ 中，我们可以自定义比较函数，完成多关键字的排序，而在 Python 中进行多关键字排序时，不同关键字的排序方式必须保持一致。我们可以将 vid 从字符转换为对应的 ASCII 码，并用其相反数作为第二关键字，这样就与第一关键字保持一致，即都进行降序排序。

在排序完成后，我们将每一个键值对中的键 vid 依次加入到答案字符串 ans 中，即可得到最终的答案。

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    string rankTeams(vector<string>& votes) {
        int n = votes.size();
        // 初始化哈希映射
        unordered_map<char, vector<int>> ranking;
        for (char vid: votes[0]) {
            ranking[vid].resize(votes[0].size());
        }
        // 遍历统计
        for (const string& vote: votes) {
            for (int i = 0; i < vote.size(); ++i) {
                ++ranking[vote[i]][i];
            }
        }
        
        // 取出所有的键值对
        using PCV = pair<char, vector<int>>;
        vector<PCV> result(ranking.begin(), ranking.end());
        // 排序
        sort(result.begin(), result.end(), [](const PCV& l, const PCV& r) {
            return l.second > r.second || (l.second == r.second && l.first < r.first);
        });
        string ans;
        for (auto& [vid, rank]: result) {
            ans += vid;
        }
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        n = len(votes[0])
        # 初始化哈希映射
        ranking = collections.defaultdict(lambda: [0] * n)
        # 遍历统计
        for vote in votes:
            for i, vid in enumerate(vote):
                ranking[vid][i] += 1
        
        # 取出所有的键值对
        result = list(ranking.items())
        # 排序
        result.sort(key=lambda x: (x[1], -ord(x[0])), reverse=True)
        return "".join([vid for vid, rank in result])

复杂度分析

  • 时间复杂度：O(NK + N^2\log N)，其中 N 是数组 votes 中每一个字符串的长度（参与排名的人数），K 是数组 votes 的长度（参与投票的人数）。「遍历统计」的时间复杂度为 O(NK)，「排序」的时间复杂度为 O(N^2\log N)（其中 O(N\log N) 为排序本身的时间，还需要额外的比较两个键值对大小的 O(N) 时间），建立最终答案字符串的时间复杂度为 O(N)，因此总时间复杂度为 O(NK + N^2\log N)。

  • 空间复杂度：O(N^2)。哈希映射中键值对的数量为 N，每个键使用 O(1) 的空间，每个值使用 O(N) 的空间，空间复杂度为 O(N^2)。存储排序的结果同样需要使用 O(N^2) 的空间，因此总空间复杂度为 O(N^2)。

 Comments
On this page
1366-通过投票对团队排名