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