LEETCODE 1366. 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"
解释:只有一个投票者,所以排名完全按照他的意愿。

示例 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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1366

解题思路分析:

这道题的排名规则与奥运会的金牌榜很相似,排在第一的肯定是是金牌数最多的国家,如果金牌数相同,查看银牌数最多,银牌数也相同则查看铜牌数量。都相同的情况下查看国家名字的字典顺序。而本题则是将奖牌改成了排名,而最多有26支队伍参赛,每一个投票可以看做是一个项目的排名情况,题目默认所有队伍都会参加所有比赛。这样一来我们可以通过题目给出的votes数组,统计出每个队伍最终获得排名的情况。即每只队伍分别获得了多少个第一名,多少个第二名,。。。多少个最后一名。这组数据可以使用一个二维数组来表示,第一维代表队伍,第二维代表名次,而二维数组的值代表该队伍取得该名次的次数。

接下来的工作就是对这个数组进行排序,我们可以将这个数组想象成一张数据库的表,order by的优先顺序是从第一列到最后一列降序,再对队伍名称进行升序排列。因为要考虑到队伍名称,所以我们需要在数组第二维中多加一列,该列存储队伍名称信息(将大写字母转为数字存储)。另外事先我们不知道有哪些队伍参加比赛,因此默认所有队伍名称为-1。

排序完成后,我们只要将每行中代表队名的列组合起来(值为-1的除外)即是返回结果。

实现代码:

public String rankTeams(String[] votes) {
    // 队伍数量
    int teamNum=votes[0].length();
    // 统计"奖牌榜"
    int[][] count=new int[26][27];
    // 最后一列代表队名,先将所有队名设置为-1
    for(int i=0;i<26;i++){
        count[i][26]=-1;
    }
    // 循环每一个投票结果
    for(int i=0;i<votes.length;i++){
        // 当前投票
        String vote=votes[i];
        // 循环投票的每一顺位
        for(int j=0;j<teamNum;j++){
            // 获得第j位的队伍
            int team=vote.charAt(j)-'A';
            // 当前队伍获得第j位的数量加一
            count[team][j]++;
            // 将当前行的最后一列,定义为当前队名
            count[team][26]=team;
        }
    }
    // 排序
    Arrays.sort(count,(a,b)->{
       // 获得高名次次数降序排列
       for(int i=0;i<26;i++){
           if(a[i]!=b[i]) return b[i]-a[i];
       }
       // 获得名次都相同时,按照队名升序排列
       return a[26]-b[26];
    });
    // 将排序好的数组的最后一列(队名)按顺序输出
    StringBuilder sb =new StringBuilder();
    for(int i=0;i<26;i++){
        // 如果队名是-1,代表当前队伍没有参加比赛,退出
        if(count[i][26]==-1) break;
        sb.append((char)(count[i][26]+'A'));
    }
    return sb.toString();
}

本题解法执行时间为4ms。

Runtime: 4 ms, faster than 95.18% of Java online submissions for Rank Teams by Votes.

Memory Usage: 40.8 MB, less than 100.00% of Java online submissions for Rank Teams by Votes.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1366-rank-teams-by-votes-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。