2024.4.12力扣每日一题——找到冠军 I

本文主要是介绍2024.4.12力扣每日一题——找到冠军 I，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目来源

力扣每日一题；题序：2923

我的题解

方法一 哈希表

哈希表存储不可能是冠军的队伍，最后没在哈希表中的队伍就是冠军。

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

public int findChampion(int[][] grid) {Set<Integer> set=new HashSet<>();int n=grid.length;for(int i=0;i<n;i++){if(set.contains(i))continue;for(int j=0;j<n;j++){if(grid[i][j]==1){set.add(j);}}}int res=0;for(int i=0;i<n;i++){if(!set.contains(i)){res=i;break;}}return res;
}

方法二 列式遍历+统计

按列遍历，统计值为1的个数，个数为n-1的就是冠军

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

public int findChampion(int[][] grid) {int n=grid.length;int res=0;for(int i=0;i<n;i++){int count=0;for(int j=0;j<n;j++){if(i!=j&&grid[i][j]==1)count++;}if(count==n-1){res=i;break;}}return res;
}

方法三 列式遍历优化+统计

按列遍历，直接计算一列的和，和为n-1的就是冠军

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

public int findChampion(int[][] grid) {int n=grid.length;int res=0;for(int i=0;i<n;i++){int count=0;for(int j=0;j<n;j++){count+=grid[i][j];}if(count==n-1){res=i;break;}}return res;
}

有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~

这篇关于2024.4.12力扣每日一题——找到冠军 I的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---