https://leetcode.cn/problems/find-champion-i/description/

二维数组的遍历。时间复杂度n²。不确定能不能只用一次循环就做出来。

func findChampion(grid [][]int) int {
    team_num:=len(grid)
    team:=make([]int,team_num)
    for i:=0;i<team_num;i++{
        for j:=0;j<team_num;j++{
            if grid[i][j]==1{
                team[j]=1
            }
        }
    }
    for i:=0;i<team_num;i++{
        if team[i]==0{
            return i
        }
    }
    return -1
}

然后看了看别人的题解，发现时间复杂度为n的思路之前在哪见过。

https://white-night.club/index.php/2023/11/19/ad158/

func findChampion(grid [][]int) int {
    result:=0
    for i:=1;i<len(grid);i++{
        if grid[i][result]==1{
            result=i
        }
    }
    return result
}

遍历一次就行。这个思路也不会出现“错过”的情况，毕竟用嵌套循环就是为了遍历所有数组，防止“错过”某个数据。接下来解释下为什么不会“错过”。

首先是对角线，因为x队不可能比它自己强，所以像[0][0]，[1][1]这种在对角线上的肯定全为0。再然后是“反转”，如果[0][1]=0，那么[1][0]一定为1。而我们要找的就是只有对角线上的元素[x][x]=0的数组，也就是说这个数组的和为n-1。

再给个样例方便理解。可以看得出来，这个矩阵是上下反转的，即条件：对于满足 i != j 的所有 i, j ，grid[i][j] != grid[j][i] 均成立。

而且由于条件：生成的输入满足：如果 a 队比 b 队强，b 队比 c 队强，那么 a 队比 c 队强，所以一定有一队是最弱的，即数组和为0。

还是这个样例，先假设队伍0是最强的，那么[1][0]=0，不符合，所以队伍1是最强的。

再往下看，如果队伍1是最强的，那么[2][1]=0，符合，所以队伍1还是最强的。

最后一组，[3][1]=1，所以队伍3比队伍1强，那么队伍3是最强的。

又由于队伍1比队伍0和队伍2都强，那么[3][0]和[3][2]的数据实际上我们可以直接忽略掉不看。相当于两两比较找更强的，那么最后留下的那个一定是最强的。这也是为什么只用一次循环就能搞定的原因。