题目链接
关键词
- 数组
- 归纳
解析
- 从题目看,grid是一个n个队伍比赛结果的二维矩阵,其中
- grid[i][j] == 1:表示i胜利
- grid[i][j] == 0:表示j胜利
- i ≠ j:自己跟自己不能比
- 解法一:
- 统计每一场比赛的胜利方,并将其胜利次数记录下来
- 最后遍历找出胜利次数最多的胜利发,即为冠军
- 解法二:
- 由于比赛只有胜负两种情况,没有打平等情况,且由于不能和自己比赛,此时一个队伍能胜利的最多场次为 n-1,所以,可以做以下分析:
- 冠军有败绩:此时冠军的胜场次数最大为n-2,意味着有其他队伍比冠军还强,此时n-2必定不是冠军的获胜次数
- 冠军没败绩:冠军全胜,获胜场数为n-1
- 经过上面的分析,冠军的获胜场数一定是n-1,反过来,获胜场数为n-1的队伍,一定为冠军
- 对于每个队伍,都统计其获胜,如果获胜场数为n-1,意味着找到了冠军,直接返回
- 解法三:
- 根据解法二的分析,冠军一定不会有败绩,且队伍强弱之前是有传递关系的,这意味着当grid[i][j] = 1, grid[j][k] = 1时,一定有grid[i][k] = 1
- 所以,可以从一个获胜方champion开始,一路往上找能战胜champion的队伍,最后的胜利者就是冠军
代码
暴力统计
统计冠军
冠军不会失败
- Author:CoderWdd
- URL:https://www.wuinsights.top//article/01HV8MQK3XAZ46M2T11DAG19Q1
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts
