LeetCode 2923. 找到冠军 I——更好的解法

上一篇博客：LeetCode 2923. 找到冠军 I——每日一题

原题链接：LeetCode 2923. 找到冠军 I

更优的解法

 今天看了一下昨天每日一题的题解，发现了更好的解法只需要 O ( n ) {O(n)} O(n) 的时间复杂度就可以解出，而不是像我上一篇博客一样需要 O ( n 2 ) {O(n^2)} O(n2) 的时间复杂度才可以解决。

 具体的思路是这样的，这个本质上就是 打擂台，如果当前的队伍输了那么该队伍就不可能是冠军，所以我们只需要一开始假设 0队 是冠军，然后与 1队 进行 PK。如果 grid[1][0] == 1 说明1队获胜，那么0队就不可能是冠军。再用1队与2队进行PK，赢了就继续与3队PK，输了说明也不是冠军，再用2队与后面的队伍PK，直到与所有的队伍PK完就可以得出冠军队伍。简而言之就是 冠军不能输！。

解题代码

class Solution {
    public int findChampion(int[][] grid) {
        int n = grid.length;
        int champion = 0;
        for (int i = 1; i < n; i++) {
            if (grid[i][champion] == 1) {
                champion = i;
            }
        }
        return champion;
    }
}

---

题解参考

• LeetCode @oamuuvyi