JZX轻语：简

LeetCode 1366 - 通过投票对团队排名

发表于2024年12月29日

#排序

排序题，考察点在于如何实现排序规则。首先使用字典（由于队伍最多为26个，可以使用列表模拟字典）统计每个队伍的得票情况，然后根据字典转换为列表，排序规则为：按照得票情况降序排列，如果得票情况相同，则按照队伍名称的字典序升序排列。最后将排序后的队伍名称连接起来即可。

C++的实现比较复杂些，首先统计得票情况，然后使用lambda表达式实现排序规则，最后将排序后的队伍名称连接起来即可。为了方便得到队伍名称，可以在得票情况列表最后添加队伍编号。

class Solution {
public:
    string rankTeams(vector<string>& votes) {
        int n = votes[0].size();
        vector<vector<int>> infos(26, vector<int>(n + 1));
        // infos[i][j]表示队伍i在第j个位置的得票情况
        // infos[i][n]表示队伍i的编号
        for (int i = 0; i < 26; ++i) infos[i][n] = i;

        for (const auto &vote : votes) {
            for (int i = 0; i < n; ++i) {
                ++infos[vote[i] - 'A'][i];
            }
        }
        // 排序规则：按照得票情况降序排列，如果得票情况相同，则按照队伍名称的字典序升序排列
        std::sort(
            infos.begin(), infos.end(),
            [n](const auto& item1, const auto& item2) {
                for (int i = 0; i < n; ++i) { if (item1[i] > item2[i]) return true; else if (item1[i] < item2[i]) return false; }
                return item1[n] < item2[n];
            }
        );
        // 将排序后的队伍名称连接起来
        std::string ans;
        for (int i = 0; i < n; ++i) {
            ans += ('A' + infos[i][n]);
        }
        return ans;
    }
};

Python可以使用defaultdict统计得票情况，然后转换为元组列表，排序规则为：按照得票情况降序排列，如果得票情况相同，则按照队伍名称的字典序升序排列。最后连接起来即可。

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        n = len(votes[0])
        info_map = defaultdict(lambda: [0] * n)
        for vote in votes:
            for i in range(n):
                c = info_map[vote[i]]
                # 使用负数计数, 这样排序的时候, 会变成从大到小排了, 而且字母是顺着排的
                c[i] -= 1
    
        return ''.join(ch for *_, ch in sorted((*info_map[ch], ch) for ch in info_map))

闪念标签：LC

题目链接：https://leetcode.cn/problems/rank-teams-by-votes/