求比赛名次 【微软面试100题 第三十六题】 - tractorman - 博客园
n支队伍比赛,分别编号为0,1,2,...,n-1,已知它们之间的实力对比关系存储在一个二维数组w[n][n]中,w[i][j]的值代表编号为i,j的队伍中更强的一支,所以w[i][j] = i或者j.
现在给出它们的出场顺序,并存储在数组order[n]中,比如order[n] = {4,3,5,8,1......},那么第一轮比赛就是4对3,5对8.胜者晋级,败者淘汰,同一轮淘汰的所有队伍排名不再细分,即可以随便排,下一轮由上一轮的胜者按照顺序,再一次两两比,比如可能是4对5,直至出现第一名。
编程实现,给出二维数组w,一维数组order和用于输出比赛名次的数组result[n],求result.
题目分析:
假设出场次序为:1 3 4 2 0 5,实力图和过程讲解如下图:
i j=i+1
Read full article from 求比赛名次 【微软面试100题 第三十六题】 - tractorman - 博客园
n支队伍比赛,分别编号为0,1,2,...,n-1,已知它们之间的实力对比关系存储在一个二维数组w[n][n]中,w[i][j]的值代表编号为i,j的队伍中更强的一支,所以w[i][j] = i或者j.
现在给出它们的出场顺序,并存储在数组order[n]中,比如order[n] = {4,3,5,8,1......},那么第一轮比赛就是4对3,5对8.胜者晋级,败者淘汰,同一轮淘汰的所有队伍排名不再细分,即可以随便排,下一轮由上一轮的胜者按照顺序,再一次两两比,比如可能是4对5,直至出现第一名。
编程实现,给出二维数组w,一维数组order和用于输出比赛名次的数组result[n],求result.
题目分析:
假设出场次序为:1 3 4 2 0 5,实力图和过程讲解如下图:
常见的思路肯定是模拟。
用一个临时数组保存本轮winner胜利的人,loser存到result中,倒着存。
特别注意w比较的是w[tmp[i][[tmp[i+1]]而不是w[i][i+1]。
另外一定要先存loser,再改tmp,否则。。你懂的。
void match(int w[MAX][MAX], int* order, int* result, int n)
{
int tb = n;
int tmp[MAX];
int lose = n-1;
int win = 0;
int i;
memcpy(tmp, order, sizeof(int)*n);
while(tb>1)
{
win = 0;
for(i=0;i<tb && (i+1)<tb;i+=2)
{
if(w[tmp[i]][tmp[i+1]]==tmp[i])
{
result[lose--] = tmp[i+1];
tmp[win++] = tmp[i];
}else
{
result[lose--] = tmp[i];
tmp[win++] = tmp[i+1];
}
}
if(tb%2==1)
{
tmp[win++] = tmp[tb-1];
}
tb = win;
for(i=0;i<tb;i++)
{
printf("%d ", tmp[i]);
}
printf("\n");
}
result[0] = tmp[0];
}
void Calc(int ppW[][N],int *pOrder,int *pResult,int n) { if(ppW==NULL || *ppW==NULL || pOrder==NULL || pResult==NULL || n<=0) return ; int nCurPos = n-1; vector<int> vectOrder; for(int i = 0;i<n;i++) vectOrder.push_back(pOrder[i]); while(vectOrder.size()>1) { for(vector<int>::iterator j = vectOrder.begin();j!=vectOrder.end();j++) { if(j+1 != vectOrder.end()) { if(ppW[*j][*(j+1)] == *j) { pResult[nCurPos--] = *(j+1); vectOrder.erase(j+1); } else { pResult[nCurPos--] = *j; //这句话的意思就是删除j,返回值是j的后一位,把该位重新赋值给j j = vectOrder.erase(j); } } } } if(vectOrder.size()==1) pResult[nCurPos--] = *(vectOrder.begin()); }xfinitytv.comcast.net
(1) 建立order的一头一尾两个指针,i,j。
(2) 头尾指针每次移动两位,移动后指向的队伍需要跟下一个队伍比赛。也就是order[i]和order[i+1]比赛; order[j]和order[j-1]比赛。然后将尾指针两队中的获胜者跟头指针中两队的失败者互换。即是:loser[order[i]]win[order[i+1]] 与win[order[j]]win[order[j+1]]。
在这里根据参加比赛的队伍总数n的不同需要讨论几种特殊情况:
a).n是4的倍数。停止条件为:i>j
i i+1 i i+1 j-1 j j-1 j
b). n是偶数但不是4的倍数。停止条件为i>j
c). n是奇数字。那么最初的尾指针为j=n-1,也就是把最后一支队轮空。
最后要把最后一个元素再换到前面去(黑色),因为它轮空了。
(3) 前i个元素再次进行相似的运算。直到n=1;
(4) 注意当j=i+1的时候需要保证胜利的队在序列的前面。
(5) 注意当数组元素为3的时候,i指向的元素跟轮空的元素(第三个元素)是相等的。而我们期望的是失败的元素(第二个元素)跟第三个元素进行互换。这种情况比较特殊,当且仅当只剩下3个元素的时候才会发生,所以需要用一段程序进行一定的修改。
Read full article from 求比赛名次 【微软面试100题 第三十六题】 - tractorman - 博客园