[LeetCode] 1366. Rank Teams by Votes 通过投票对团队排名

In a special ranking system, each voter gives a rank from highest to lowest to all teams participating in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

You are given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return a string of all teams sorted by the ranking system.

Example 1:

Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation:
Team A was ranked first place by 5 voters. No other team was voted as first place, so team A is the first team.
Team B was ranked second by 2 voters and ranked third by 3 voters.
Team C was ranked second by 3 voters and ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team, and team B is the third.

Example 2:

Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation:
X is the winner due to the tie-breaking rule. X has the same votes as W for the first position, but X has one vote in the second position, while W does not have any votes in the second position.

Example 3:

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: Only one voter, so their votes are used for the ranking.

Constraints:

• 1 <= votes.length <= 1000
• 1 <= votes[i].length <= 26
• votes[i].length == votes[j].length for 0 <= i, j < votes.length.
• votes[i][j] is an English uppercase letter.
• All characters of votes[i] are unique.
• All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

这道题给了一个排名系统，每张选票把不同的候选者进行排名，最终对候选者进行投票统计的方法是，首先数其排在第一位的票数，若得票最多，就在最终排名上放在第一，若有两个候选者排在第一位的票数相同，则比较第二位的票数，并以此类推进行排名，若排最后还是没有分出胜负，则按名字的字母顺序进行排序。题意并不是很难理解，这里的候选者的名字就用大写的单个字母进行代替了，每张选票就是就是一个字符串，且长度相等。由于候选者出现的位置很重要，要按不同位置来统计每个候选者的得票数，题目中限定了最多只有 26 个候选者，那么排位就有 26 个，每个候选者都需要一个长度为 26 的数组来统计每个排位上的得票数。

这里用个小 trick，由于题目中所有若各个排名都相同的话，则使用候选者的名字进行排序，所以这里用 27 个位置，最后一个位置放候选人的名字，排序起来非常方便。这里就建立一个大小为 26 by 27 的二维数组 cnt，其中 cnt[i][j] 表示候选者i在第j个位置上的得票数，当然 cnt[i][26] 除外，是候选者字母的 ASCII 码值。由于并不是每次都有 26 个候选者，所以只需要把存在的候选者的名字加入到第 27 个位置中，可以遍历第一张选票的候选者，直接加入字符的 ASCII 码即可。接下来就是统计票数了，遍历每一张选票，对于每一张遍历到的选票，遍历每一个位置，将该位置上的值减去1，这里为啥不是对应票数加1呢，这里实际上也是用了一个小 trick，因为排序是默认从小到大，而我们想让得票数高的排在前面，就可以用负数。唱票完成后，就可以直接组成想要返回的字符串即可，参见代码如下：

class Solution {
public:
    string rankTeams(vector<string>& votes) {
        string res;
        vector<vector<int>> cnt(26, vector<int>(27));
        for (char c : votes[0]) {
            cnt[c - 'A'][26] = c;
        }
        for (string vote : votes) {
            for (int i = 0; i < vote.size(); ++i) {
                --cnt[vote[i] - 'A'][i];
            }
        }
        sort(cnt.begin(), cnt.end());
        for (int i = 0; i < votes[0].size(); ++i) {
            res += cnt[i][26];
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1366

类似题目：

Online Election

参考资料：

https://leetcode.com/problems/rank-teams-by-votes

https://leetcode.com/problems/online-election/solutions/173382/c-java-python-binary-search-in-times/

LeetCode All in One 题目讲解汇总(持续更新中...)