问题

循环赛每个队对战所有其他对手， 胜利者记3分， 失败者记1分. 两个数组做为输入， competitions，存放主场队和客场队， results存放结果， 1表示主队获胜， 0表示客队获胜。返回分数最高的队伍。

解答

使用一个hash表，key为队伍名称， 值为累计分数。时间复杂度O(n) 循环赛的数量， 空间复杂度O(k), 参赛队数量。对应hash表需要的容量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def tournamentWinner(competitions, results):
    currentBestTeam = ""
    scores = {currentBestTeam: 0}
    
    for idx, competition in enumerate(competitions):
        result = results[idx]
        homeTeam, awayTeam = competition
        
        winningTeam = homeTeam if result == 1 else awayTeam
        
        updateScores(winningTeam, 3 , scores)
        
        if scores[winningTeam] > scores[currentBestTeam]:
            currentBestTeam = winningTeam
            
    return currentBestTeam

def updateScores(team, points, scores):
    if team not in scores:
        scores[team] = 0
    scores[team] += points

 

参考及引用

图片from Akihito Ichiyama