应用于 n x n 矩阵的分而治之算法问题

Question

共有 n 名棋手参加了国际象棋锦标赛。特别是每对玩家 i 和 j 都玩一场游戏。锦标赛的所有结果都编码在 n × n 矩阵 A 中，其中对于每对不同的玩家 A[i, j] 以以下方式编码 i 和 j 所玩游戏的结果：

A[i, j] = 选项 1：如果我赢了，我 选项2：0平局 选项 3：如果 j 获胜则 j

如果玩家 d 赢得了所有比赛，我们就说她是超级冠军。我们想要一个接收 A 作为输入并返回超级冠军 d（如果存在）的算法。如果没有超级冠军，则算法必须返回 0。 给出该任务的分治算法。获得 O(n log n) 就足够了。在您的算法中，将矩阵 A 视为全局变量是完全可以的，这样它就不需要包含在每个递归调用的输入中。

我假设每个玩家都与其他玩家玩过一次。此外，对角线将包含 0，因为每个玩家都不能与自己对战，并且矩阵将是对称的。另外，我认为基本情况是我们只有一名球员，所以该球员将成为超级冠军。但是，我不知道如何检查超级玩家，即如何在没有双 for 循环的情况下检查矩阵的行和列，这将导致 O(n^2)。

非常感谢任何帮助或提示。

Answer 1

有

n²

游戏结果（因此您的输入大小为

O(n²)

）。
由于输入没有排序或具有一些其他结构，您可以利用它来避免至少读取所有输入一次，因此您找不到比

O(n²)

更好的算法