c***2
发帖数: 838 | 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;i
if(*max
im=i;
*max=a[i];
}
if(im==0)
im2=1;
else
im2=0;
*max2=a[im2];
for(i=0;i
if((i!=im) && (*max2
*max2=a[i];
im2=i;
}
} |
