Easy

题目描述

有 n 支队伍参加锦标赛，编号从 0 到 n - 1。

给你一个下标从 0 开始的二维布尔矩阵 grid，大小为 n * n。对于满足 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 队强

解题思路

解题思路

这是一道关于图论和矩阵的简单题目。我们需要找到能够击败所有其他队伍的冠军队伍。

方法一：统计每行的1的个数（推荐）

  • 对于队伍 i，如果它是冠军，那么它必须比其他所有队伍都强
  • 这意味着第 i 行应该有 n-1 个 1（除了 grid[i][i] = 0）
  • 我们可以遍历每一行，统计1的个数，找到个数为 n-1 的行

方法二：统计每列的1的个数

  • 换个角度思考，如果队伍 j 是冠军，那么所有其他队伍都不能击败它
  • 这意味着第 j 列应该全部是 0（除了 grid[j][j] = 0）
  • 找到列和为 0 的列即可

方法三：直接验证

  • 对每个队伍，检查它是否能击败所有其他队伍
  • 时间复杂度较高，但思路最直观

根据题目保证，冠军是唯一存在的，所以我们采用方法一，它最直观且高效。

代码实现

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

class Solution:
    def findChampion(self, grid: List[List[int]]) -> int:
        n = len(grid)
        for i in range(n):
            if sum(grid[i]) == n - 1:
                return i
        return -1

public class Solution {
    public int FindChampion(int[][] grid) {
        int n = grid.Length;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    count++;
                }
            }
            if (count == n - 1) {
                return i;
            }
        }
        return -1;
    }
}

var findChampion = function(grid) {
    const n = grid.length;
    
    for (let i = 0; i < n; i++) {
        let isChampion = true;
        for (let j = 0; j < n; j++) {
            if (i !== j && grid[j][i] === 1) {
                isChampion = false;
                break;
            }
        }
        if (isChampion) {
            return i;
        }
    }
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n²)
空间复杂度O(1)

说明：

  • 时间复杂度：需要遍历整个 n×n 的矩阵，在最坏情况下需要检查所有元素
  • 空间复杂度：只使用了常数额外空间来存储计数器和循环变量