本文主要是介绍思维题,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 = 0for i, row in enumerate(grid):if row[ret]:ret = ireturn 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;}
};
这篇关于思维题,LeetCode 2923. 找到冠军 I的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!