[讨论］如何写出只要用小过三次的LOOP就能找到最大值和最小值

小劲鸭

粽子兄的倒让我想起了用black-red tree的办法， 其实也是O(logn)...可以考虑。。:p
AVL树操作起来颇麻烦， 最大的障碍就是每删除一个internal node就要reconstruct一次。。。到现在我都不太会用。

zonzi

black-red tree的办法无法想像怎么把最大/小值找出来，看到这题第一个想到的就是avl了，其实如果模块变得好的话，用c,avl还是很好实现的......
用java就不知道了，觉得不能用一个array来实现此类树......

小劲鸭

最初由 zonzi 发表
black-red tree的办法无法想像怎么把最大/小值找出来，看到这题第一个想到的就是avl了，其实如果模块变得好的话，用c,avl还是很好实现的......
用java就不知道了，觉得不能用一个array来实现此类树......

这倒好办， 做个class myAVL implements interface AVL, CLASS里面加个vector， 加个node就行了。

zonzi

最初由 小劲鸭 发表
这倒好办， 做个class myAVL implements interface AVL, CLASS里面加个vector， 加个node就行了。

也是，快用avl吧，不要忘记加个counter来记有多少次比较哦

acdy

1. 
   
2. /*
   
3. * Created on 2004-6-26
   
4. * MaxMin.java
   
5. */
   
6. 
   
7. /**
   
8. * @author acdy
   
9. * 算法 2.6 递归求取最大和最小元素
   
10. */
    
11. public class MaxMin {
    
12. 
    
13.         private int n;
    
14.         private double[] A;
    
15.         private double fmax;
    
16.         private double fmin;
    
17.        
    
18.         public MaxMin(double[] A) {
    
19.                 this.A = A;
    
20.                 n = A.length -1;
    
21.         }
    
22.         // 递归求取最大和最小元素
    
23.         public void maxMin(int i,int j) {
    
24.         // 把最大A(i,j)中的最大值和最小值分别赋给fmax和fmin
    
25.                
    
26.                 if(i==j) {
    
27.                         fmax = fmin = A[i];
    
28.                 }
    
29.                 else if(i==j-1) {
    
30.                         if(A[i]<A[j]) {
    
31.                                 fmax = A[j];fmin = A[i];
    
32.                         }
    
33.                         else {
    
34.                                 fmax = A[i];fmin = A[j];
    
35.                         }
    
36.                 }
    
37.                 else {
    
38.                         int mid = (int)Math.floor((i+j)/2);
    
39.                         double gmax,gmin,hmax,hmin;
    
40.                         maxMin(i,mid);
    
41.                         gmax = fmax;
    
42.                         gmin = fmin;
    
43.                        
    
44.                         maxMin(mid+1,j);
    
45.                         hmax = fmax;
    
46.                         hmin = fmin;
    
47.                        
    
48.                         fmax = Math.max(gmax,hmax);
    
49.                         fmin = Math.min(gmin,hmin);
    
50.                 }
    
51.         }
    
52.        
    
53.         // 显示结果
    
54.         public void print() {
    
55.                 System.out.println("最大值为:\t"+ fmax);
    
56.                 System.out.println("最小值为:\t"+ fmin);
    
57.         }
    
58.         public static void main(String[] args) {
    
59.                 // 下标从一开始
    
60.                 double[] A={0,22,13,-5,-8,15,60,17,31,47};
    
61.                 // 初始化
    
62.                 MaxMin test = new MaxMin(A);
    
63.                
    
64.                 // 递归求取最大和最小元素
    
65.                 test.maxMin(1,A.length-1);
    
66.                
    
67.                 // 显示结果
    
68.                 test.print();
    
69.         }
    
70. }
    

复制代码

需要比较的次数

T(n) =
0 (n=1)
1 (n=2)
T(floor(n/2))+T(ceil(n/2)) + 2 (n>2)

当n = 2 的幂时 T(n)=2T(n/2)+2 ;3n/2-2 是最好,平均及最坏情况的比较次数