Medium

题目描述

在一个特殊的排名系统中，每个投票者将所有参与竞争的团队从高到低进行排名。

团队的排序由获得最多第一名票数的团队决定。如果两个或更多团队在第一名位置平局，我们考虑第二名位置来解决冲突，如果他们再次平局，我们继续这个过程直到平局被解决。如果两个或更多团队在考虑所有位置后仍然平局，我们根据他们的团队字母按字母顺序排名。

给定一个字符串数组 votes，表示排名系统中所有投票者的投票。根据上述排名系统对所有团队进行排序。

返回按排名系统排序的所有团队的字符串。

示例 1:

输入: votes = ["ABC","ACB","ABC","ACB","ACB"]
输出: "ACB"
解释: 
团队 A 被 5 个投票者排在第一位。没有其他团队被投票为第一位，所以团队 A 是第一名。
团队 B 被 2 个投票者排在第二位，被 3 个投票者排在第三位。
团队 C 被 3 个投票者排在第二位，被 2 个投票者排在第三位。
由于大多数投票者将 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
  • 对于 0 <= i, j < votes.length，votes[i].length == votes[j].length
  • votes[i][j] 是英文大写字母
  • votes[i] 的所有字符都是唯一的
  • votes[0] 中出现的所有字符也出现在 votes[j] 中，其中 1 <= j < votes.length

解题思路

这道题的核心思路是统计每个团队在各个位置的得票数，然后根据题目描述的规则进行排序。

解题步骤：

  1. 统计得票数：为每个团队建立一个数组，记录其在每个排名位置的得票数。使用哈希表存储 团队字母 -> [位置0得票数, 位置1得票数, ...]

  2. 自定义排序：根据题目规则设计比较函数：

    • 优先比较第1位的得票数（降序）
    • 如果平局，比较第2位的得票数（降序）
    • 依此类推，直到所有位置比较完
    • 如果所有位置得票数都相同，按团队字母升序排列

  3. 构建结果：将排序后的团队字母拼接成字符串返回

时间复杂度分析：统计得票数需要 O(m×n)，其中 m 是投票数，n 是团队数；排序需要 O(n²×n) = O(n³)，因为比较函数最坏情况下需要比较 n 个位置。总时间复杂度为 O(m×n + n³)。

空间复杂度：使用哈希表存储每个团队的得票数组，空间复杂度为 O(n²)。

代码实现

class Solution {
public:
    string rankTeams(vector<string>& votes) {
        int n = votes[0].length();
        unordered_map<char, vector<int>> count;
        
        // 初始化每个团队的得票数组
        for (char c : votes[0]) {
            count[c] = vector<int>(n, 0);
        }
        
        // 统计每个位置的得票数
        for (const string& vote : votes) {
            for (int i = 0; i < n; i++) {
                count[vote[i]][i]++;
            }
        }
        
        // 获取所有团队字母
        vector<char> teams;
        for (char c : votes[0]) {
            teams.push_back(c);
        }
        
        // 自定义排序
        sort(teams.begin(), teams.end(), [&](char a, char b) {
            // 比较每个位置的得票数
            for (int i = 0; i < n; i++) {
                if (count[a][i] != count[b][i]) {
                    return count[a][i] > count[b][i];
                }
            }
            // 如果所有位置得票数相同，按字母顺序排序
            return a < b;
        });
        
        return string(teams.begin(), teams.end());
    }
};

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        n = len(votes[0])
        count = {}
        
        # 初始化每个团队的得票数组
        for c in votes[0]:
            count[c] = [0] * n
        
        # 统计每个位置的得票数
        for vote in votes:
            for i, team in enumerate(vote):
                count[team][i] += 1
        
        # 获取所有团队字母并排序
        teams = list(votes[0])
        teams.sort(key=lambda x: ([-count[x][i] for i in range(n)], x))
        
        return ''.join(teams)

public class Solution {
    public string RankTeams(string[] votes) {
        int n = votes[0].Length;
        var count = new Dictionary<char, int[]>();
        
        // 初始化每个团队的得票数组
        foreach (char c in votes[0]) {
            count[c] = new int[n];
        }
        
        // 统计每个位置的得票数
        foreach (string vote in votes) {
            for (int i = 0; i < n; i++) {
                count[vote[i]][i]++;
            }
        }
        
        // 获取所有团队字母
        var teams = votes[0].ToCharArray();
        
        // 自定义排序
        Array.Sort(teams, (a, b) => {
            // 比较每个位置的得票数
            for (int i = 0; i < n; i++) {
                if (count[a][i] != count[b][i]) {
                    return count[b][i].CompareTo(count[a][i]);
                }
            }
            // 如果所有位置得票数相同，按字母顺序排序
            return a.CompareTo(b);
        });
        
        return new string(teams);
    }
}

var rankTeams = function(votes) {
    const n = votes[0].length;
    const count = new Map();
    
    // 初始化每个团队的得票数组
    for (const c of votes[0]) {
        count.set(c, new Array(n).fill(0));
    }
    
    // 统计每个位置的得票数
    for (const vote of votes) {
        for (let i = 0; i < n; i++) {
            count.get(vote[i])[i]++;
        }
    }
    
    // 获取所有团队字母并排序
    const teams = votes[0].split('');
    teams.sort((a, b) => {
        // 比较每个位置的得票数
        for (let i = 0; i < n; i++) {
            if (count.get(a)[i] !== count.get(b)[i]) {
                return count.get(b)[i] - count.get(a)[i];
            }
        }
        // 如果所有位置得票数相同，按字母顺序排序
        return a.localeCompare(b);
    });
    
    return teams.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m×n + n³)m 是投票数，n 是团队数。统计得票 O(m×n)，排序 O(n³)
空间复杂度O(n²)哈希表存储每个团队的 n 个位置得票数

相关题目