c++ - O(N) 中的锦标赛获胜者和 O(NLogN) 中的玩家排名

Question

在 N 名球员的网球锦标赛中，每个球员都与其他球员一起比赛。 以下条件始终成立- 如果玩家 P1 赢得了与 P2 的比赛，并且玩家 P2 赢得了 P3，那么玩家 P1 也击败了 P3。 在 O(N) 时间和 O(1) 空间内找到锦标赛的获胜者。在 O(NlogN) 时间内找到玩家的排名。 我的解决方案: 输入是一个 bool 矩阵，其中元素 matrix[i][j] 表示玩家 i 是否赢得玩家 j。

bool win[][]= {
    {0, 0, 1, 1, 1, 0, 1},
    {1, 0, 1, 1, 1, 1, 1},
    {0, 0, 0, 1, 1, 0, 0},
    {0, 0, 0, 0, 1, 0, 0},
    {0, 0, 0, 0, 0, 0, 0},
    {1, 0, 1, 1, 1, 0, 1},
    {0, 0, 1, 1, 1, 0, 0}
};

这样就可以找到获胜者，

int winner = 0;
for (int i = 1; i < PLAYER_COUNT; ++i) {
    if (win[i][winner])
        winner = i;
}
return winner;

为了获得玩家的排名，我想拓扑排序会是一个不错的选择。如果玩家 1 赢得玩家 2，则添加一条边，就像这个 P1-> P2。如果玩家 1 在这里获胜，那么它对所有其他玩家都有优势。然后以获胜者为源顶点进行拓扑排序，将给出玩家的排名。 我的解决方案正确吗？还有其他有效的解决方案吗？任何帮助都会很棒，提前致谢。

Answer 1

条件

If player P1 has won the match with P2 and player P2 has won from P3

定义总排序，即如果我们定义 P1 < P2对于“P2 击败了 P1 ”，我们有一个传递顺序关系 < , 可以完全用作常规 less-than排序或寻找最大值的关系。所以对于实现我们可以定义谓词bool lessThan(int p1, int p2)这将简单地查找 p1和 p2 O(1) 中矩阵的关系.然后使用谓词进行“最大”搜索，它是线性的 (O(N))，或者用于排序(排名)，它是 O(N log N) .