d**e
发帖数: 6098 | 1 【 以下文字转载自 InterviewHackers 俱乐部 】
发信人: htd (孩儿她爹), 信区: InterviewHackers
标 题: zz 讨论一道笔试题
发信站: BBS 未名空间站 (Mon Sep 27 13:29:23 2010, 美东)
发信人: xuekai (又四年), 信区: Algorithm
标 题: 讨论一道笔试题
发信站: 水木社区 (Tue Sep 28 00:40:28 2010), 站内
有2~k个足球队进行单淘汰比赛，各个队伍间的胜负关系用矩阵w[i][j]表示，例如队伍
0
与队伍3的胜者是3，则a[0][3]与a[3][0]都是3。队伍间的签位用order[n]表示，最终的
比赛排名用result[n]来表示，下面给出一列：
有4只队伍参加比赛，w[i][j]={{0,1,2,3},{1,1,2,1},{2,2,2,3},{3,1,3,3}}
签位向量order[4]={0,1,2,3}
则首先队伍0与队伍1比赛，1胜出，然后2与3比赛，3胜出，第二轮1与3比赛，1胜出，则
result[4]={1,3,0,2} 其中队伍0与2 | t****a
发帖数: 1212 | 2 O(n) time, O(n) space (just the result vector)
void game(int w[][], int order[], int result[], int n) {
# compare 1 v 2, 3 v 4, 5 v 6 and fill the losers to the tail of result,
and winners to the head of order
# recursively invoke game(w, order, result, n/2)
# until n = 0
} | p********7
发帖数: 549 | 3 这个需要复杂算法么？
从order向量依次获得比赛结果，我觉得可以把上层结果输入到一个新的vector，
比如先order是 2，3，5，6，4，1，0
新的order就是 win(2,3),win(5,6),win(4,1),0
把loser 压入一个stack
然后再次执行上面的代码，till order只有1个元素，stack里面就是要的结果 | d**e
发帖数: 6098 | 4 感觉这个主意不错。
但我觉得losers放后面，winner放前面这一步不容易做。
losers的顺序没关系，但winner的顺序又要保持和原来一致。
Array[n]，奇数序号的放在 0 - n/2，偶数序号的放在
n/2 + 1 -- n，而且保持原有顺序不变，能否可以O(n)做得到？
【在 t****a 的大作中提到】
: O(n) time, O(n) space (just the result vector)
: void game(int w[][], int order[], int result[], int n) {
: # compare 1 v 2, 3 v 4, 5 v 6 and fill the losers to the tail of result,
: and winners to the head of order
: # recursively invoke game(w, order, result, n/2)
: # until n = 0
: }
| d**e
发帖数: 6098 | 5 我觉得也是除了result外，额外需要O(n)的空间，再加O(n)的时间。
【在 p********7 的大作中提到】
: 这个需要复杂算法么？
: 从order向量依次获得比赛结果，我觉得可以把上层结果输入到一个新的vector，
: 比如先order是 2，3，5，6，4，1，0
: 新的order就是 win(2,3),win(5,6),win(4,1),0
: 把loser 压入一个stack
: 然后再次执行上面的代码，till order只有1个元素，stack里面就是要的结果
| f***g
发帖数: 214 | | d**e
发帖数: 6098 | 7 应该是差不多，我觉得相当于构造一个binary tree
【在 f***g 的大作中提到】
: Loser tree?
| m**q
发帖数: 189 | 8 这个好像是可以做的
每次比较把winner放在奇数序号，把loser放在偶数序号，
然后再做一次quick sort的partition，就把winner全都
swap到前面，loser全部放到后面去了；
然后记住有多少个winner，再进行下一轮...
【在 d**e 的大作中提到】
: 感觉这个主意不错。
: 但我觉得losers放后面，winner放前面这一步不容易做。
: losers的顺序没关系，但winner的顺序又要保持和原来一致。
: Array[n]，奇数序号的放在 0 - n/2，偶数序号的放在
: n/2 + 1 -- n，而且保持原有顺序不变，能否可以O(n)做得到？
|
|
