1366. Rank Teams by Votes

2024-12-30

字数统计: 1.3k字 | 阅读时长: 7min

QUESTION：

1366. Rank Teams by Votes.md
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 <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= 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 in votes[j] where 1 <= j < votes.length.

My Think：

This question requires us to count their votes. The first thing that comes to mind is to build a double structure, similar to this:
这道题要求我们统计他们的投票情况. 首先想到的就是构建一个双重结构体, 类似于这样:

type struct {
    char A {
        1: 1;
        2: 1;
        3: 1;
    }
}

Then fill in the dictionary in a double loop and sort it. It’s very simple in Python, but I thought it was complicated at first and built the sorting logic manually.
Finally, we can use lambda expression sorted_teams = sorted(rank.keys(), key = lambda x: ([-rank[x][i] for i in range(len(votes[0]))], x))

What needs to be noted in Go is the usage of the standard answer. Use slices.SortedFunc to sort the teams. The sorting rules are defined according to the requirements of the question:

Sort in descending order by votes.
If the votes are the same, sort in ascending alphabetical order.
maps.Keys(cnts) gets the keys of all teams (that is, the characters of all teams)
slices.Compare(cnts[b], cnts[a]): compare the vote slices of two teams and sort in descending order by votes (b comes first).
cmp.Compare(a, b): when the votes are the same, sort in ascending alphabetical order.
cmp.Or: execute the first comparison rule. If the return value is not 0 (that is, there is a priority difference), return directly; otherwise execute the next rule.

然后在一个双重循环中填写这个字典, 最后进行排序即可. 在Python中十分简单, 但是我一开始想复杂了, 手动构建了排序逻辑.
最后用lambda表达式即可sorted_teams = sorted(rank.keys(), key = lambda x: ([-rank[x][i] for i in range(len(votes[0]))], x))

Go里需要注意的是标准答案的用法, 使用 slices.SortedFunc 对团队进行排序，排序规则按题目要求定义：

按票数降序排列。
如果票数相同，按字母升序排列。
maps.Keys(cnts) 获取所有团队的键（即所有团队的字符）
slices.Compare(cnts[b], cnts[a])：比较两个团队的票数切片，按票数降序排列（b 在前）。
cmp.Compare(a, b)：当票数相同时，按字母升序排列。
cmp.Or：执行第一个比较规则，如果返回值非 0（即有优先级差异），直接返回；否则执行下一个规则。

Code：

class Solution:
    def rankTeams(self, votes: List[str]) -> str:
        rank = defaultdict(lambda: defaultdict(int))
        for value in votes:
            for ind, c in enumerate(value):
                rank[c][ind] += 1
        sorted_teams = sorted(rank.keys(), key = lambda x: ([-rank[x][i] for i in range(len(votes[0]))], x))
        return ''.join(sorted_teams)

def rankTeams_Siz(self, votes: List[str]) -> str:
        rank = defaultdict(lambda: defaultdict(int))
        for value in votes:
            for ind, c in enumerate(value):
                rank[c][ind] += 1
        print(rank)
        ans = ''
        for i in range(len(votes[0])):
            temp_ans = ''
            count = 0
            for key, value in rank.items():
                if value[i] > count:
                    temp_ans = key
                    count = value[i]
                else:
                    # 如果并列, 则考虑下一位 If there is a tie, consider the next one
                    while value[i] == count:
                        i += 1 # 这个i是临时变量, 直接用 This i is a temporary variable, use it directly
                        if i > len(votes[0]): # 考虑找到最后都没找到的情况Consider the situation where you find nothing in the end.
                            # 答案值应该是字母顺序 The answer values should be in alphabetical order
                            temp_ans = key
                            break
                        if value[i] > count:
                            temp_ans = key
                            count = value[i]
            ans += temp_ans
        return ans

func rankTeams(votes []string) string {
    cnts:=map[rune][]int{}
    for _,ch := range votes[0] {
        cnts[ch]=make([]int,len(votes[0]))
    }

    for _,vote := range votes{
        for i,ch := range vote{
            cnts[ch][i]++
        }
    }

    res := slices.SortedFunc(maps.Keys(cnts),func(a,b rune) int{
        return cmp.Or(slices.Compare(cnts[b],cnts[a]),cmp.Compare(a,b))
    })
    return string(res)
}

package main

import "sort"

func rankTeams(votes []string) string {
	rank := make(map[byte]map[int]int)

	for _, vote := range votes {
		for i := 0; i < len(vote); i++ {
			team := vote[i]
			if _, ok := rank[team]; !ok {
				rank[team] = make(map[int]int)
			}
			rank[team][i]++
		}
	}

	teams := make([]byte, 0, len(rank))
	for team := range rank {
		teams = append(teams, team)
	}

	sort.Slice(teams, func(i, j int) bool {
		a, b := teams[i], teams[j]
		for k := 0; k < len(votes[0]); k++ {
			// 比较两队在 k 排位的票数 // Compare the votes of the two teams in position k
			countA, countB := rank[a][k], rank[b][k]
			if countA != countB {
				return countA > countB // 按票数降序 Sort by votes in descending order
			}
		}
		return a < b // 字母升序 Alphabetical ascending
	})
	// 拼接结果
	return string(teams)
}