【2024.04.12】LeetCode每日一题·找到冠军 I

2024年04月12日 11时04分

标签： LeetCode 数组递推 Easy

## 题目描述

一场比赛中共有`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`队将会是**冠军**。

返回这场比赛中将会成为冠军的队伍。

#### 示例1
````
输入：grid = [[0,1],[0,0]]
输出：0
解释：比赛中有两支队伍。
grid[0][1] == 1 表示 0 队比 1 队强。所以 0 队是冠军。
````

#### 示例2
````
输入：grid = [[0,0,1],[1,0,1],[0,0,0]]
输出：1
解释：比赛中有三支队伍。
grid[1][0] == 1 表示 1 队比 0 队强。
grid[1][2] == 1 表示 1 队比 2 队强。
所以 1 队是冠军。
````

#### 提示
````
n == grid.length
n == grid[i].length
2 <= n <= 100
grid[i][j] 的值为 0 或 1
对于所有 i， grid[i][i] 等于 0.
对于满足 i != j 的所有 i, j ，grid[i][j] != grid[j][i] 均成立
生成的输入满足：如果 a 队比 b 队强，b 队比 c 队强，那么 a 队比 c 队强
````

#### 来源

> 来源：力扣（LeetCode）
> 
> 链接：[2923. 找到冠军 I](https://leetcode.cn/problems/find-champion-i/description/?envType=daily-question&envId=2024-04-12)

## 解题思路1
由于最强的队伍一定能够击败所有的其他队伍，因此其对应行的元素除了其本身外，其他均为`1`，总和一定为`n-1`，因此遍历`grid`的每一行即可。

时间复杂度：$$O(n^2)$$

### 代码
````cpp
class Solution {
public:
    int findChampion(vector<vector<int>>& grid) {
        int res;
        for(int i = 0; i < grid.size(); i++){
            int sum = 0;
            for(int j = 0; j < grid[0].size(); j++){
                sum += grid[i][j];
            }
            if(sum == grid[i].size()-1){
                res = i;
                break;
            }
        }
        return res;
    }
};
````

### 用时和内存
> 执行用时：54 ms，在所有C++提交中击败了72.02%的用户
>
> 内存消耗：38.88 MB，在所有C++提交中击败23.85%的用户
> 
 
## 解题思路2:递推
如果我们记`0~i`队中的冠军为`res`，那么如何求`0~i+1`队的冠军？

如果`i+1`队弱于`res`，那么冠军仍然为`res`；如果`i+1`队强于`res`，那么由于实力的传递性，冠军应该为`i+1`

这样，只需要遍历所有队伍即可，时间复杂度$$O(n)$$

### 代码
````cpp
class Solution {
public:
    int findChampion(vector<vector<int>>& grid) {
        int res = 0;
        // res := 遍历[0,i]区间内的最强队，一开始为0队
        // 接着：依次比对每一队是否强过第一名的队
        // 因为排名具有传递关系，因此：如果当前第一名强过已经遍历过的所有队，那么如果后面出现一个队比当前的第一名更强，那么该队会比之前遍历的所有队都强
        // 因此，只要不断更新最强的队即可
        for(int i = 0; i < grid.size(); i++){
            if(grid[res][i] == 0) res = i;
        }
        return res;
    }
};
````

### 用时和内存
> 执行用时：58 ms，在所有C++提交中击败了52.75%的用户
>
> 内存消耗：38.86 MB，在所有C++提交中击败28.44%的用户
>

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【2024.04.12】LeetCode每日一题·找到冠军 I

所有评论

暂无评论

新增评论