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

发布时间：2020-12-16 03:37:35 所属栏目：百科来源：网络整理

导读：在N个球员的网球锦标赛中,每个球员都与其他球员一起比赛. 以下条件始终如下─ 如果玩家P1赢得了与P2的比赛并且玩家P2从P3获胜,那么玩家P1也击败了P3. 在O(N)时间和O(1)空间中找到锦标赛的冠军.在O(NlogN)时间内找到玩家的等级. 我的解决方案输入是布尔矩阵,

在N个球员的网球锦标赛中,每个球员都与其他球员一起比赛.
以下条件始终如下─
如果玩家P1赢得了与P2的比赛并且玩家P2从P3获胜,那么玩家P1也击败了P3.
在O(N)时间和O(1)空间中找到锦标赛的冠军.在O(NlogN)时间内找到玩家的等级.
我的解决方案
输入是布尔矩阵,其中元素矩阵[i] [j]指示玩家i是否赢得玩家j.

bool win[][]= {
    {0,1,1},{1,{0,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在这里获胜,那么它将与所有其他玩家有优势.然后以获胜者作为源顶点的拓扑排序将给出玩家的等级.
我的解决方案是否正确还有其他有效的解决方案吗？任何帮助都会很棒,提前谢谢.

解决方法

条件

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!