| comments | difficulty | edit_url | rating | source | tags | |||||
|---|---|---|---|---|---|---|---|---|---|---|
true |
Medium |
1626 |
Weekly Contest 178 Q2 |
|
In a special ranking system, each voter gives a rank from highest to lowest to all teams participating 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.
You are 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 ranked third by 3 voters. Team C was ranked second by 3 voters and 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 the tie-breaking rule. X has the same votes as W for the first position, but X has one vote in the second position, while W does not have any votes in the second position.
Example 3:
Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"] Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK" Explanation: Only one voter, so their votes are used for the ranking.
Constraints:
1 <= votes.length <= 10001 <= votes[i].length <= 26votes[i].length == votes[j].lengthfor0 <= i, j < votes.length.votes[i][j]is an English uppercase letter.- All characters of
votes[i]are unique. - All the characters that occur in
votes[0]also occur invotes[j]where1 <= j < votes.length.
For each candidate, we can count the number of votes they receive at each rank, then compare the vote counts for different ranks in order. If the vote counts are the same, we compare the letters.
The time complexity is
class Solution:
def rankTeams(self, votes: List[str]) -> str:
m = len(votes[0])
cnt = defaultdict(lambda: [0] * m)
for vote in votes:
for i, c in enumerate(vote):
cnt[c][i] += 1
return "".join(sorted(cnt, key=lambda c: (cnt[c], -ord(c)), reverse=True))class Solution {
public String rankTeams(String[] votes) {
int m = votes[0].length();
int[][] cnt = new int[26][m + 1];
for (var vote : votes) {
for (int i = 0; i < m; ++i) {
++cnt[vote.charAt(i) - 'A'][i];
}
}
Character[] s = new Character[m];
for (int i = 0; i < m; ++i) {
s[i] = votes[0].charAt(i);
}
Arrays.sort(s, (a, b) -> {
int i = a - 'A', j = b - 'A';
for (int k = 0; k < m; ++k) {
if (cnt[i][k] != cnt[j][k]) {
return cnt[j][k] - cnt[i][k];
}
}
return a - b;
});
StringBuilder ans = new StringBuilder();
for (var c : s) {
ans.append(c);
}
return ans.toString();
}
}class Solution {
public:
string rankTeams(vector<string>& votes) {
int m = votes[0].size();
array<array<int, 27>, 26> cnt{};
for (const auto& vote : votes) {
for (int i = 0; i < m; ++i) {
++cnt[vote[i] - 'A'][i];
}
}
string s = votes[0];
ranges::sort(s, [&](char a, char b) {
int i = a - 'A', j = b - 'A';
for (int k = 0; k < m; ++k) {
if (cnt[i][k] != cnt[j][k]) {
return cnt[i][k] > cnt[j][k];
}
}
return a < b;
});
return string(s.begin(), s.end());
}
};func rankTeams(votes []string) string {
m := len(votes[0])
cnt := [26][27]int{}
for _, vote := range votes {
for i, ch := range vote {
cnt[ch-'A'][i]++
}
}
s := []rune(votes[0])
sort.Slice(s, func(i, j int) bool {
a, b := s[i]-'A', s[j]-'A'
for k := 0; k < m; k++ {
if cnt[a][k] != cnt[b][k] {
return cnt[a][k] > cnt[b][k]
}
}
return s[i] < s[j]
})
return string(s)
}function rankTeams(votes: string[]): string {
const m = votes[0].length;
const cnt: number[][] = Array.from({ length: 26 }, () => Array(m + 1).fill(0));
for (const vote of votes) {
for (let i = 0; i < m; i++) {
cnt[vote.charCodeAt(i) - 65][i]++;
}
}
const s: string[] = votes[0].split('');
s.sort((a, b) => {
const i = a.charCodeAt(0) - 65;
const j = b.charCodeAt(0) - 65;
for (let k = 0; k < m; k++) {
if (cnt[i][k] !== cnt[j][k]) {
return cnt[j][k] - cnt[i][k];
}
}
return a.localeCompare(b);
});
return s.join('');
}impl Solution {
pub fn rank_teams(votes: Vec<String>) -> String {
let m = votes[0].len();
let mut cnt = vec![vec![0; m + 1]; 26];
for vote in &votes {
for (i, ch) in vote.chars().enumerate() {
cnt[(ch as u8 - b'A') as usize][i] += 1;
}
}
let mut s: Vec<char> = votes[0].chars().collect();
s.sort_by(|&a, &b| {
let i = (a as u8 - b'A') as usize;
let j = (b as u8 - b'A') as usize;
for k in 0..m {
if cnt[i][k] != cnt[j][k] {
return cnt[j][k].cmp(&cnt[i][k]);
}
}
a.cmp(&b)
});
s.into_iter().collect()
}
}