在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在这里获胜,那么它将与所有其他玩家有优势.然后以获胜者作为源顶点的拓扑排序将给出玩家的等级.
我的解决方案是否正确还有其他有效的解决方案吗？任何帮助都会很棒,提前谢谢.
解决方法
条件
If player P1 has won the match with P2 and player P2 has won from P3
定义总排序,即如果我们定义P1<对于“P2失败P1”的P2,我们有一个传递有序关系< ;,它可以完全用作排序或找到最大值的常规小于关系.因此,对于实现,我们可以定义谓词bool lessThan(int p1,int p2),它将简单地在O(1)中的矩阵中查找p1和p2关系.然后使用谓词进行“最大”搜索,即线性(O(N)),或者用于排序(排名),即O(N log N).
