LeetCode 1366. 通过投票对团队排名 哈希排序

摘要:
如果在考虑所有投票情况后仍有并列,球队将根据球队字母的字母顺序进行排名。这是代表所有选民排名的字符串数组选票。请根据以上排名规则对所有球队进行排名。由于C队“排名第二”的票数较多,C队排名第二,B队排名第三。X队和W队的“排名第一”票数相同,但X队有一票“排名第二”,而W队没有获得“第二”。

地址 https://leetcode-cn.com/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"
解释:只有一个投票者,所以排名完全按照他的意愿。
示例 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

 

算法1
题目有点长 主要是创建一个结构体 对每队在1-26名获得投票做记录
然后进行排序(投票可能有1000的范围,但是可投票的队伍最多26个,可排的名次最多也就26个)

class Solution {
public:
    struct Node{
        char c;
        int rank[26];
    };
    struct Node vv[26];
    
    void InsertRank(string s){
        for(int i = 0;i < s.size();i++){
            int idx = s[i]-'A';
            vv[idx].c = s[i];
            vv[idx].rank[i]++;
        }
    }
    
    static bool cmp(const  struct Node& a,const  struct Node& b){
        for(int i = 0; i < 26;i++){
            if(a.rank[i] > b.rank[i] ) return true;
            if(a.rank[i] < b.rank[i])  return false;
        }
        
        return a.c < b.c;
    }
    
    string rankTeams(vector<string>& votes) {
        if(votes.empty()) return "";
        if(votes.size()==1) return votes[0];
        
        memset(vv,0,sizeof(struct Node)*26);
        
        for(int i = 0; i < votes.size();i++){
            InsertRank(votes[i]);
        }
        
        sort(vv,vv+26,cmp);
        string ans;
        for(int i = 0; i< votes[0].size();i++){
            ans += vv[i].c;
        }
        
        return ans;
    }
};

免责声明:文章转载自《LeetCode 1366. 通过投票对团队排名 哈希排序》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇C#探秘系列(七):XML文件操作(一)ubuntu查看系统资源占用(内存,cpu和进程)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

数据库性能优化

MySQL基础表和数据 数据库访问优化法则 了解计算机系统的硬件基本性能指标,可以快速找到SQL的性能瓶颈点,下面是当前主流计算机性能指标数据。 从图上可以看到基本上每种设备都有两个指标: 延时(响应时间):表示硬件的突发处理能力; 带宽(吞吐量):代表硬件持续处理能力。 从上图可以看出,计算机系统硬件性能从高到代依次为: CPU——Cache(L1-L...

MySQL高级知识(八)——ORDER BY优化

前言:在使用order by时,经常出现Using filesort,因此对于此类sql语句需尽力优化,使其尽量使用Using index。 0.准备 #1.创建test表。 drop table if exists test; create table test( id int primary key auto_increment, c1 var...

Mysql 查询优化,索引原理与慢查询优化。

Mysql 查询优化 索引原理与慢查询优化 一 介绍 为什么要有索引? 一般的应用程序,读写比例在10:左右,而且插入操作和一般的更新操作很少出现性能问题, 在生产环境中,我们遇到最多的,也是最容易出问题的,还是一些复杂的查询操作,因此对查询, 我们必定要去优化它们,那我们怎么去优化呢?那就要提到索引了。 什么是索引? 索引在MySQL中也叫做“...

MySQL查询截取分析

一、查询优化 1,mysql的调优大纲 慢查询的开启并捕获 explain+慢SQL分析 show profile查询SQL在Mysql服务器里面的执行细节和生命周期情况 SQL数据库服务器的参数调优 2,小表驱动大表 mysql的join实现原理是,以驱动表的数据为基础,“嵌套循环”去被驱动表匹配记录。驱动表的索引会失效,而被驱动表的索引有效。 #假...

对字符串进行快速排序(即字符数组排序)

package com.cn.gao; import java.util.Scanner; //对字符串进行快速排序 public class CharsQuickSort { public static final int SIZE=100; //可以输入的最大字符数 //快速排序的一次划分 public s...

redis 数据类型详解 以及 redis适用场景场合

1.  MySql+Memcached架构的问题     实际MySQL是适合进行海量数据存储的,通过Memcached将热点数据加载到cache,加速访问,很多公司都曾经使用过这样的架构,但随着业务数据量的不断增加,和访问量的持续增长,我们遇到了很多问题:   1.MySQL需要不断进行拆库拆表,Memcached也需不断跟着扩容,扩容和维护工作占据大量...