O(N)锦标赛冠军和O(NLogN)球员排名

Question

在N个球员的网球锦标赛中,每个球员都与其他球员一起比赛.以下条件始终保持 - 如果玩家P1赢得了与P2的比赛并且玩家P2从P3获胜,那么玩家P1也击败了P3.在O(N)时间和O(1)空间中找到锦标赛的冠军.在O(NlogN)时间内找到玩家的等级. 我的解决方案: 输入是一个布尔矩阵,其中元素矩阵[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,那么添加边缘lke这个P1-> P2.如果玩家1在这里获胜,那么它将与所有其他玩家有优势.然后以获胜者作为源顶点的拓扑排序将给出玩家的等级.我的解决方案是否正确 还有其他有效的解决方案吗？任何帮助都会很棒,提前谢谢.

Answer 1

条件

如果玩家P1赢得了与P2的比赛并且玩家P2赢得了P3

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