首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 1366. 通过投票对团队排名(自定义排序)

LeetCode 1366. 通过投票对团队排名(自定义排序)

作者头像
Michael阿明
发布2020-07-13 17:26:07
1.2K0
发布2020-07-13 17:26:07
举报

1. 题目

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

排名规则如下:

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

给你一个字符串数组 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"
解释:只有一个投票者,所以排名完全按照他的意愿。

示例 4:
输入:votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]
输出:"ABC"
解释: 
A 队获得两票「排位第一」,两票「排位第二」,两票「排位第三」。
B 队获得两票「排位第一」,两票「排位第二」,两票「排位第三」。
C 队获得两票「排位第一」,两票「排位第二」,两票「排位第三」。
完全并列,所以我们需要按照字母升序排名。

示例 5:
输入:votes = ["M","M","M","M"]
输出:"M"
解释:只有 M 队参赛,所以它排名第一。 

提示:
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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/rank-teams-by-votes 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 题目意思:类似奥运会金牌榜排名
vector<vector<int>> c;
bool cmp(char& a, char& b)
{
    for(int j = 0; j < 26; j++)
    {
        if(c[a-'A'][j] == c[b-'A'][j])
            continue;
        return c[a-'A'][j] > c[b-'A'][j];
    }
    return a < b;
}
class Solution {
public:
    string rankTeams(vector<string>& votes) {
        int i, j;
        c.clear();//全局变量记得清空,leetcode每次调用不会清空
        vector<int> t(26,0);
        for(i = 0; i < 26; ++i)
            c.push_back(t);
        for(i = 0; i < votes.size(); i++)
        {
            for(j = 0; j < votes[i].size(); j++)
                c[votes[i][j]-'A'][j]++;
        }
        sort(votes[0].begin(), votes[0].end(), cmp);
        return votes[0];
    }
};
  • lambda表达式简洁,注意!!![&]里面写&才可以识别外部变量,表示以引用传入
class Solution {
public:
    string rankTeams(vector<string>& votes) {
        int i, j;
        vector<vector<int>> c(26,vector<int>(26,0));
        for(i = 0; i < votes.size(); i++)
        {
            for(j = 0; j < votes[i].size(); j++)
                c[votes[i][j]-'A'][j]++;
        }
        sort(votes[0].begin(), votes[0].end(), [&](auto a, auto b){
        	for(int j = 0; j < 26; j++)
		    {
		        if(c[a-'A'][j] == c[b-'A'][j])
		            continue;
		        return c[a-'A'][j] > c[b-'A'][j];
		    }
		    return a < b;
        });
        return votes[0];
    }
};
在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-03-01 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 解题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档