算法分析的作业题 急啊~~

Question

给定数组a[0:n-1],试设计一个算法,在最坏情况下用n+[logn]-2次比较找出a[0:n-1] 中的元素的最大值和次大值.后天交 急求啊 用什么语言都行   这门课没怎么听（悲剧）在线等。。谢谢了

Answer 1

public class NumCom{
public static void main (String[] args) {
int[] num={4,5,6,3,2,67,34,23,32,120,45};
int n1=-9999999,n2=-999999;
for(int i=0;i<num.length;i++){
if(n1<num[i]){
n2=n1;
n1=num[i];

}
else if(n2<num[i]){
n2=num[i];
}

}
System.out.println ("maxNum="+n1);
System.out.println ("secNum="+n2);
    }
}

Answer 2

貌似在最坏情况下用n+[logn]-2次比较找出还达不到....
期待高手...

Answer 3

如果忽略元素的移动，可以用堆排序的原理，建一个大顶堆，建堆过程中，不用调整子堆。
最大元素就是堆顶，次大元素就是堆顶的两个孩子中的最大者。
元素比较次数：n次。算法如下：
import java.util.*;public class MaxNextMax{
public static void main(String[] args){
int n=40;             //元素个数
int[] a=new int[n+1];  //a[0]不用。
int max,nextMax;
Random r=new Random();
for(int i=1;i<=n;i++){
a[i]=r.nextInt(300);   //产生0~300这间的随机数
System.out.print(" "+a[i]);
}
System.out.println("");
int start=n/2;
int temp;
if(n%2==0){
if(a[start]<a[start*2]){
temp=a[start];
a[start]=a[start*2];
a[start*2-1]=temp;
}
start--;
}
for(int i=start;i>0;i--){
if(a[i]<a[2*i]){
temp=a[2*i];
a[2*i]=a[i];
a[i]=temp;
}
if(a[i]<a[2*i+1]){
temp=a[2*i+1];
a[2*i+1]=a[i];
a[i]=temp;
}
}
max=a[1];
if(a[2]>a[3]){
nextMax=a[2];
}else{
nextMax=a[3];
}
System.out.println("Max: "+max+"\nnext Max: "+nextMax);


  }
}