1366.通过投票对团队排名

【LetMeFly】1366.通过投票对团队排名：自定义排序

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

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

排名规则如下：

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

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

解题方法：统计 + 自定义排序

创建哈希表counts，其中counts[i][j]代表团队i + 'A'排位第j + 1的次数。

然后排序时按照题意自定义排序规则即可。

• 时间复杂度$O(nm+n^2\log n)$，其中有$n$个参与者，$m$个投票者
• 空间复杂度$O(nC)$，其中$C=26$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2024-12-29 14:17:03
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2024-12-29 14:24:20
 */

class Solution {
public:
    string rankTeams(vector<string>& votes) {
        int voter = votes.size(), voted = votes[0].size();
        vector<vector<int>> counts(26, vector<int>(voted));
        for (string& vote : votes) {
            for (int i = 0; i < voted; i++) {
                counts[vote[i] - 'A'][i]++;
            }
        }
        string ans = votes[0];
        sort(ans.begin(), ans.end(), [&](const char& a, const char& b) {
            vector<int>& va = counts[a - 'A'], &vb = counts[b - 'A'];
            for (int i = 0; i < voted; i++) {
                if (va[i] != vb[i]) {
                    return va[i] > vb[i];
                }
            }
            return a < b;
        });
        return ans;
    }
};

Python

'''
Author: LetMeFly
Date: 2024-12-29 14:58:42
LastEditors: LetMeFly.xyz
LastEditTime: 2024-12-29 21:08:46
'''
"""
from typing import List

class Solution:    
    def rankTeams(self, votes: List[str]) -> str:
        n = len(votes[0])
        counts = [[0] * n for _ in range(26)]
        for vote in votes:
            for i in range(n):
                counts[ord(vote[i]) - ord('A')][i] -= 1
        return ''.join(sorted(votes[0], key=lambda a: (counts[ord(a) - ord('A')], a)))

Java

/*
 * @Author: LetMeFly
 * @Date: 2024-12-29 21:09:49
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2024-12-30 02:16:01
 */
// 好复杂
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public String rankTeams(String[] votes) {
        int n = votes[0].length();
        int[][] counts = new int[26][n];
        for (String vote : votes) {
            for (int i = 0; i < n; i++) {
                counts[vote.charAt(i) - 'A'][i]++;
            }
        }
        Character[] charList = new Character[n];
        for (int i = 0; i < n; i++) {
            charList[i] = votes[0].charAt(i);
        }
        Arrays.sort(charList, new Comparator<Character>() {
            @Override
            public int compare(Character a, Character b) {
                int c = Arrays.compare(counts[b - 'A'], counts[a - 'A']);
                return c == 0 ? a - b : c;
            }
        });
        String ans = new String();
        for (Character c : charList) {
            ans += c;
        }
        return ans;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2024-12-30 09:20:50
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2024-12-30 13:20:36
 */
package main
import "sort"

func rankTeams(votes []string) string {
    counts := make(map[byte][]int)
    for _, c := range votes[0] {
        counts[byte(c)] = make([]int, len(votes[0]))
    }
    for _, vote := range votes {
        for i, v := range vote {
            counts[byte(v)][i]++
        }
    }
    ans := []byte(votes[0])
    sort.Slice(ans, func(a, b int) bool {
        countA, countB := counts[ans[a]], counts[ans[b]]
        for i := range ans {
            if countA[i] != countB[i] {
                return countA[i] > countB[i]
            }
        }
        return ans[a] < ans[b]
    })
    return string(ans)
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/144814103