思维题，LeetCode 2923. 找到冠军 I

一、题目

1、题目描述

一场比赛中共有 n 支队伍，按从 0 到  n - 1 编号。

给你一个下标从 0 开始、大小为 n * n 的二维布尔矩阵 grid 。对于满足 0 <= i, j <= n - 1 且 i != j 的所有 i, j ：如果 grid[i][j] == 1，那么 i 队比 j 队 强 ；否则，j 队比 i 队 强 。

在这场比赛中，如果不存在某支强于 a 队的队伍，则认为 a 队将会是 冠军 。

返回这场比赛中将会成为冠军的队伍。2923. 找到冠军 I

2、接口描述

python3

​

class Solution:
    def findChampion(self, grid: List[List[int]]) -> int:

cpp

​

class Solution {
public:
    int findChampion(vector<vector<int>>& grid) {
        
    }
};

3、原题链接

2923. 找到冠军 I

二、解题报告

1、思路分析

我们假定冠军是0

那么从第一行开始枚举 i ，如果grid[i][0] = 1，那么更新冠军为i，继续从i + 1行找比i强的

因为前i - 1行没有比0强的，而i强于0，故从i + 1行接着枚举即可

2、复杂度

时间复杂度： O(n)空间复杂度：O(n)

3、代码详解

python3

​

class Solution:
    def findChampion(self, grid: List[List[int]]) -> int:
        ret = 0
        for i, row in enumerate(grid):
            if row[ret]:
                ret = i
        return ret
        

cpp

​

class Solution {
public:
    int findChampion(vector<vector<int>>& grid) {
        int ret = 0;
        for(int i = 1, n = grid.size(); i < n; i++)
            if(grid[i][ret]) ret = i;
        return ret;
    }
};