Tournament winner

问题

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

解答

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

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

 

Comments are closed.