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

博客园 - Grandyang

[LeetCode] 1372. Longest ZigZag Path in a Binary Tree 二叉树中的最长交错路径 [LeetCode] 1371. Find the Longest Substring Containing Vowels in Even Counts 每个元音包含偶数次的最长子字符串 [LeetCode] 1370. Increasing Decreasing String 上升下降字符串 [LeetCode] 1368. Minimum Cost to Make at Least One Valid Path in a Grid 使网格图至少有一条有效路径的最小代价 [LeetCode] 1367. Linked List in Binary Tree 二叉树中的链表 [LeetCode] 1365. How Many Numbers Are Smaller Than the Current Number 有多少小于当前数字的数字 [LeetCode] 1363. Largest Multiple of Three 形成三的最大倍数 [LeetCode] 1362. Closest Divisors 最接近的因数 [LeetCode] 1361. Validate Binary Tree Nodes 验证二叉树 [LeetCode] 1360. Number of Days Between Two Dates 日期之间隔几天 [LeetCode] 1359. Count All Valid Pickup and Delivery Options 有效的快递序列数目 [LeetCode] 1358. Number of Substrings Containing All Three Characters 包含所有三种字符的子字符串数目 [LeetCode] 1357. Apply Discount Every n Orders 每隔n个顾客打折 [LeetCode] 1356. Sort Integers by The Number of 1 Bits 根据数字二进制下1 的数目排序 [LeetCode] 1354. Construct Target Array With Multiple Sums 多次求和构造目标数组 [LeetCode] 1353. Maximum Number of Events That Can Be Attended 最多可以参加的会议数目 [LeetCode] 1352. Product of the Last K Numbers 最后 K 个数的乘积 [LeetCode] 1351. Count Negative Numbers in a Sorted Matrix 统计有序矩阵中的负数 [LeetCode] 1349. Maximum Students Taking Exam 参加考试的最大学生数

Grandyang · 2024-07-06 · via 博客园 - Grandyang

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 题目讲解汇总(持续更新中...)

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

博客园 - Grandyang