2019拼多多提前批笔试 —— 票选球王
题目描述:
M 个投票者给 N 个球星评等级，等级由英文字母表示，'a'级最高，'z'级最低，共26个级别。当 [球星X的评级比Y高] 的票数高于 [球星Y的评级比X高] 的票数时，称候选球星X强于候选球星Y。若有一个候选球星强于其他所有球星，则称为球王。根据这个规则至多有一个球王，否则没有球王。请你判断哪位换选球星是球王。
输入描述：
第一行包含两个数字N、M，分别代表候选球星数量和选票数量；接下来M行，每行是一个长度为N的字符串，每个字符串表示一张选票上的信息。每个字符串的第k个字符，表示这张选票对第k个候选球星。
输出描述：
若有球王，则输出仅包含一个整数X，表示编号为X(0<=X<N)的候选球星是球王；若无球王，则输出一行仅包含一个整数-1。
示例：
思路分析：
定义两个二维char型数组input和output（类型为vector<vector<char>>），一个二维数组input用来存放输入的字符串，然后将二维字符串数组行列倒置存入第二个数组output中，则output字符串数组中的每一个字符串str为每个选票人队每个候选球星的评定等级。将每个字符串str从小到大排序（即按字母顺序'a'在最前，'z'在最后，str最小即等级最高），比较每个str的大小，如果仅有唯一一个最小的字符串，则其对应的候选球星为球王，返回字符串索引；如果最小的字符串不止一个，则不存在球王，返回-1。
代码如下：
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>using namespace std;int main()
{int N, M; // N为候选球星，M为投票者cin >> N >> M;vector<vector<char>> input(M, vector<char>(N)); // 输入字符串数组vector<vector<char>> output(N, vector<char>(M)); // 倒置字符串数组// 初始化for (int i = 0; i < M; i++){for (int j = 0; j < N; j++){cin >> input[i][j];}}// 数组倒置for (int i = 0; i < N; i++){for (int j = 0; j < M; j++){output[i][j] = input[j][i];}}// 将倒置后的字符串数组中的每个字符串排序（候选球星的选票等级）for (int i = 0; i < N; i++)sort(output[i].begin(), output[i].end());// 找出候选球星中选票等级最高的也就是最小的那个字符串即是球王vector<char> str = output[0];int index = 0; // 球王编号（索引）for (int i = 1; i < N; i++){if (str >= output[i]){str = output[i];index = i;}}// 处理候选球星中存在相同最高等级的情况int cnt = 0;for (int i = 0; i < N; i++){if (str == output[i]){cnt++;}}if (cnt>1)index = -1;cout << index << endl;return 0;
}
本文链接：https://my.lmcjl.com/post/20331.html
4 评论