1366. Rank Teams by Votes

In a special ranking system, each voter gives a rank from highest to lowest to all teams participated 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.

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 was ranked third by 3 voters.
Team C was ranked second by 3 voters and was 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 tie-breaking rule. X has same votes as W for the first position but X has one vote as second position while W doesn't have any votes as second position. 

Example 3:

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: Only one voter so his votes are used for the ranking.

Example 4:

Input: votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]
Output: "ABC"
Explanation: 
Team A was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team B was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team C was ranked first by 2 voters, second by 2 voters and third by 2 voters.
There is a tie and we rank teams ascending by their IDs.

Example 5:

Input: votes = ["M","M","M","M"]
Output: "M"
Explanation: Only team M in the competition so it has the first rank.

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 upper-case 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.

---

给定很多人对很多team的打分排序列表，如果一个队排在前面的名次越多，则其最终名次越高，据此输出最终排序列表。

规则很复杂，其实很简单。设计一个Team的类，它有一个scores数组，scores[i]表示这个队被多少人投票排在了第i名。由于最多只有26个队，所以scores的维度为26。对Team自定义排序函数，排序规则是依次比较scores的每个元素大小，如果都相等的话，最后比较name的大小。

完整代码如下：

const int MAXN = 26;
class Team {
public:
	char name;
	vector<int> scores;

	Team() :name(0) {
		scores.resize(MAXN, 0);
	};

	bool operator<(const Team& t) {
		for (int i = 0; i < MAXN; ++i) {
			if (scores[i] > t.scores[i]) {
				return true;
			}
			else if (scores[i] < t.scores[i]) {
				return false;
			}
		}
		return name < t.name;
	}
};

class Solution {
public:
	string rankTeams(vector<string>& votes) {
		vector<Team> teams(MAXN, Team());
		for (int j = 0; j < votes[0].size(); ++j) {
			int idx = votes[0][j] - 'A';
			teams[idx].name = votes[0][j]; // 出现的team name
		}
		for (int i = 0; i < votes.size();++i) {
			for (int j = 0; j < votes[i].size(); ++j) {
				int idx = votes[i][j] - 'A';
				++teams[idx].scores[j];
			}
		}
		vector<Team> showups;
		for (int i = 0; i < MAXN; ++i) {
			if (teams[i].name != 0) {
				showups.push_back(teams[i]);
			}
		}
		sort(showups.begin(), showups.end());
		string ans = "";
		for (int i = 0; i < showups.size(); ++i) {
			ans += showups[i].name;
		}
		return ans;
	}
};

本代码提交AC，用时20MS。