[LeetCode] 每日一题 1366. 通过投票对团队排名

题目链接

题目描述

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

排名规则如下：

• 参赛团队的排名次序依照其所获「排位第一」的票的多少决定。如果存在多个团队并列的情况，将继续考虑其「排位第二」的票的数量。以此类推，直到不再存在并列的情况。

• 如果在考虑完所有投票情况后仍然出现并列现象，则根据团队字母的字母顺序进行排名。

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

解释：只有一个投票者，所以排名完全按照他的意愿。

提示

• 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

题解

解题思路

题目要求根据投票人给出的排位情况，对参赛团队进行排名。我们可以通过以下步骤解决问题：

1. 统计每个团队在不同排位上的票数

   • 使用二维数组 cnt[26][m]，其中 cnt[i][j] 表示字母 i（即队伍）在第 j 排位上的票数

   • 遍历所有投票，统计每个队伍的排名情况

2. 自定义排序规则

   • 将所有候选队伍按照其「排位第一」到「排位第 m」的票数依次比较进行排序，票数多的队伍排在前面

   • 如果票数一致，则根据队伍名称的字母顺序排序

3. 构造结果字符串

   • 按照排序后的顺序，将队伍的名字拼接为结果字符串

代码实现

class Solution {
    public String rankTeams(String[] votes) {
        int m = votes[0].length(); // 候选队伍数量
        int[][] cnt = new int[26][m]; // 统计票数

        // 统计每个队伍在不同排位上的票数
        for (var vote : votes) {
            for (int i = 0; i < m; i++) {
                cnt[vote.charAt(i) - 'A'][i]++;
            }
        }
        
        // 初始化候选队伍数组
        Integer[] ansNum = new Integer[m];
        for (int i = 0; i < m; i++) {
            ansNum[i] = votes[0].charAt(i) - 'A';
        }
        
        // 自定义排序
        Arrays.sort(ansNum, (e1, e2) -> {
            for (int i = 0; i < m; i++) {
                if (cnt[e1][i] != cnt[e2][i]) {
                    return cnt[e2][i] - cnt[e1][i];
                }
            }
            // 字母序
            return e1 - e2; 
        });
        
        // 构造结果字符串
        StringBuilder ans = new StringBuilder();
        for (Integer num : ansNum) {
            ans.append((char) ('A' + num));
        }
        return ans.toString();
    }
}

复杂度分析

1. 时间复杂度

   • 统计票数的时间复杂度为 O(n × m)，其中 n 是投票数，m 是候选队伍数。

   • 排序的时间复杂度为 O(m² × log m)，因为排序时每个候选队伍比较需要耗费 O(m) 的时间。

   • 总体时间复杂度为 O(n × m + m² × log m)。

2. 空间复杂度

   • 主要使用了一个二维数组 cnt[26][m]，空间复杂度为 O(m²)。

总结

这道题通过「计数 + 自定义排序」的方式解决，重点在于正确统计每个队伍在不同排位上的票数，并设计排序规则。

适用于类似的基于优先级和排序规则的排名问题，在投票数较多时表现良好。同时，时间复杂度受投票数和队伍数的影响，要需要注意优化空间使用。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。