一组数中找max或min的最快方法是什么？

ArXoR

原帖由 emacsnw 于 4/9/07 16:25 发表


这个应该是最好的方法了，记得以前哪里看到过。

好像是算法导论里有吧?
但是仍然不知道它是不是最好...

erduo100

最好的方法就是ArXoR 说的分治法

1. 
   
2. 
   
3. void MinMax(int a[], int n, int &min, int &max)
   
4. {
   
5.     int s;
   
6.     if(n % 2)
   
7.     {
   
8.         min = max = a[0];
   
9.                 s = 1;
   
10.     }
    
11.     else
    
12.         {
    
13.                 if (a[0] > a[1])
    
14.                 {
    
15.                         min = a[1];
    
16.                         max = a[0];
    
17.                 }
    
18. 
    
19.                 else
    
20.                 {
    
21.                         min = a[0];
    
22.                         max = a[1];
    
23.                 }
    
24.                 s = 2;
    
25.         }
    
26. 
    
27.         for (int i = s; i < n; i+=2)
    
28.         {
    
29.                 if (a[i] > a[i+1])
    
30.                 {
    
31.                         if (a[i] > max)
    
32.                         {
    
33.                                 max = a[i];
    
34.                         }
    
35. 
    
36.                         if (a[i+1] < min)
    
37.                         {
    
38.                                 min = a[i+1];
    
39.                         }
    
40.                 }
    
41. 
    
42.                 else
    
43.                 {
    
44.                         if (a[i+1] > max)
    
45.                         {
    
46.                                 max = a[i+1];
    
47.                         }
    
48. 
    
49.                         if (a[i] < min)
    
50.                         {
    
51.                                 min = a[i];
    
52.                         }
    
53.                 }
    
54.         }
    
55. }
    

复制代码

比较次数约为3n/2

roywangt

可以试一试多路并归的方式算算

stephen412

LZ 你的题目没有出严谨，如果你不对于你的数组的分布情况做一个描述的话，那么别人很难给出一个有价值的答案，
你的题目的原旨应该是要求给出一个时间度最小的排序算法把！所以你需要告诉我们你的数据的分布哦！

hero--008

原帖由 zwylinux 于 2007-4-9 12:34 发表


这个不需要排序，但是也不可能比O(n)快
[code]
void maxmin(int a[], int n){
  int i,max,min;

  max=a[0];
  min=a[0];
  for (i=1;i<n;++i){
    if (a>max)
      max = a;
    e ...

这个就是比较排序法了~

yuanchengjun

O(n)
因为要照顾到每一个数，所以只能这样了，

flw

不知道你们都在讨论什么？

tyc611

原帖由 flw 于 2007-4-10 23:33 发表
不知道你们都在讨论什么？

他们都不看LZ的题目是啥。。。