找最大俩数的代码怎么写？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

找最大俩数的代码怎么写？

找最大俩数的代码怎么写？# JobHunting - 待字闺中

l*a2011-02-20 08:02

1 楼

算法大家都知道
N-1 find the biggest one
then log2n-1 find from all those compared with the biggest one just now
写代码咋写，给个例子看看吧

g*s2011-02-20 08:02

2 楼

你说的哪个题？

【在 l*****a 的大作中提到】

: 算法大家都知道
: N-1 find the biggest one
: then log2n-1 find from all those compared with the biggest one just now
: 写代码咋写，给个例子看看吧

l*a2011-02-20 08:02

3 楼

我说得还不够明确？
算法都给出来了，但是不知道怎么写，至少不用额外空间的。。

【在 g*********s 的大作中提到】

: 你说的哪个题？

g*s2011-02-20 08:02

4 楼

什么是”all those compared with the max"？难道不是每个都要做比较？

【在 l*****a 的大作中提到】

: 我说得还不够明确？
: 算法都给出来了，但是不知道怎么写，至少不用额外空间的。。

p*r2011-02-20 08:02

5 楼

真的没看懂

【在 l*****a 的大作中提到】

: 我说得还不够明确？
: 算法都给出来了，但是不知道怎么写，至少不用额外空间的。。

f*w2011-02-20 08:02

6 楼

我也没懂为什么次大只要logN

r*e2011-02-20 08:02

7 楼

两两分组直到比出最大，像一个自底向上的二叉树
次大必然在最大的直接对手中产生，对手数量就是树的高度吧

【在 f*****w 的大作中提到】

: 我也没懂为什么次大只要logN

r*e2011-02-20 08:02

8 楼

不用额外空间应该是不可能的
没法keep trace of the opponents

【在 l*****a 的大作中提到】

: 我说得还不够明确？
: 算法都给出来了，但是不知道怎么写，至少不用额外空间的。。

S*z2011-02-20 08:02

9 楼

别说那么玄乎，什么两两分组直到比出最大？
怎么分？怎么比？

【在 r*******e 的大作中提到】

: 两两分组直到比出最大，像一个自底向上的二叉树
: 次大必然在最大的直接对手中产生，对手数量就是树的高度吧

c*22011-02-20 08:02

10 楼

doing the tournament with complexity N+lgN in the cost of extra stack spaces
used for recursion
straightforward 2-pass scanning takes N-1+N-2=2N-3 with no extra space
Tournament:
void find_max_2max(int a[], int start, int end, int *max, int *max2)
{
int i, mid;
int max00,max01,max10,max11;
int temp1,temp2;

if(start==end){
*max=a[start];
*max2=a[start];
return;
}

if(end-start==1){
*max=MAX(a[start],a[end]);
*max2=MIN(a[start],a[end]);
return;
}

mid=(start+end)/2;

find_max_2max(a, start, mid, &max00, &max01);
find_max_2max(a, mid+1, end, &max10, &max11);

temp1=MAX(max00,max01);
temp2=MAX(max10,max11);

if(temp1>temp2){
*max=temp1;
*max2=MAX(temp2, MIN(max00,max01));
}
else {
*max=temp2;
*max2=MAX(temp1, MIN(max10,max11));
}
}
Scan twice:
void find_max_2max(int a[], int size, int *max, int *max2)
{
int i, im, im2;
*max=0;
*max2=0;
if(size<=0) return;
*max=a[0];
im=0;
for(i=1;iif(*maxim=i;
*max=a[i];
}
if(im==0)
im2=1;
else
im2=0;
*max2=a[im2];
for(i=0;iif((i!=im) && (*max2*max2=a[i];
im2=i;
}
}

r*e2011-02-20 08:02

11 楼

http://en.wikipedia.org/wiki/Selection_algorithm#Tournament_Alg

【在 S****z 的大作中提到】

: 别说那么玄乎，什么两两分组直到比出最大？
: 怎么分？怎么比？

g*s2011-02-20 08:02

12 楼

说说怎么跟踪和最大数直接比较过的数？最大数不是要到最后一步才知道吗？

【在 r*******e 的大作中提到】

: http://en.wikipedia.org/wiki/Selection_algorithm#Tournament_Alg

S*z2011-02-20 08:02

13 楼

其实不用跟踪吧，算法第一遍找最大的时候把二叉树层次结构都建好了
次最大只能在跟最大比较过的集合里面，
那接下来把最大数所在的叶子的值改成最小，
然后从该叶子节点开始两两比较的往上走到顶，比较出来的就是次最大了吧

【在 g*********s 的大作中提到】

: 说说怎么跟踪和最大数直接比较过的数？最大数不是要到最后一步才知道吗？