数组极值问题

1。 最坏情况下  3n/2-2  次比较可以得到数组的最大值和最小值

 max[n/2]  min[n/2]

a[1....n]  可以 a[1]  a[2]  比较得到 max[1] min[1] ,

同理 ，可以得到  max[] min[] 的值比较次数 n/2

max[] 中得到最大值 n/2-1

min[] 中得到最小值 n/2-

则总共  n/2+n/2+n/2-1-1 比较次数

 

import javax.swing.JOptionPane;

public class two15{
  public static void main(String args[])
  {
    int a[]=new int[50];//
    int min[]=new int[25];//
    int max[]=new int[25];//
    int n=0,i=0,k=1;
    String num;
    String aa[]=new String[50];
    
    num=JOptionPane.showInputDialog("enter the total num of the array");
    
    n=Integer.parseInt(num);
    
    //单个数不进行比较
    if(n!=1){
    
    for(i=0;i<n;i++)
    {
      aa[i]=JOptionPane.showInputDialog("请输入数组的每个元素");
      
      a[i]=Integer.parseInt(aa[i]);

    }
    
    //用分治法把N个数分成2/N组 每组两个进行比较，把小的放在MIN，大的放在MAX
     //最差情况下比较N/2次
  
    for(i=1;i<(n/2)*2;i=i+2)
    {
      if(a[i-1]<=a[i])
      {
        min[k-1]=a[i-1];max[k-1]=a[i];k++;
      }
      else
      {
        min[k-1]=a[i];max[k-1]=a[i-1];k++;
      }
    }
    
    
    /*在MAX中找出最大的，在MIN中找出最小的
     *最差情况下比较2*（N/2-1）次
     */
    int maxm=max[0],minm=min[0];
    
    for(k=1;k<n/2;k++)
    {
      if(max[k]>maxm) maxm=max[k];
      if(min[k]<minm) minm=min[k];
    }
    
    if(n%2!=0)//N为奇数时，还要和最后一个数比较
    {
      if(a[n-1]>maxm) maxm=a[n-1];
      if(a[n-1]<minm) minm=a[n-1];
    }
    
    JOptionPane.showMessageDialog(null,
    "最大的数是"+maxm+"最小的数是"+minm,
    "result",JOptionPane.INFORMATION_MESSAGE);
    
}
  
  else JOptionPane.showMessageDialog(null,
    "一个数无须查找","警告！"
    ,JOptionPane.INFORMATION_MESSAGE);
    
    
  }
}

 

 

2. 得到数组的最大值次大值比较次数最多  n+log(n) -2

假设 a5 最大 ，则得到一个锦标赛树

                     a5

            a1            a5

    a1        a4         a5

a1 a2    a3 a4   a5  a6

做n/2次比较，可以得到n/2个较小的数。重复做一直到只剩下一个数，即最小值。将最小值换成负无穷，沿着最小值的比较路线走上去，可以得到次小值。
循环直到产生最小值的过程会产生一棵树，而且是完全二叉树，每次比较都会产生出一个内部结点，因此总的比较次数就是树中内结点的个数。完全二叉树最坏情况下是满二叉树，有n个叶结点，因此高为O(log(n))，
内结点个数是n-1。

等比数列求和：

1+2+4+8...+n = (1-2^(log_2_n+1)) = 2n-1
第二次沿最小数的比较路径走上去，所做的比较次数就是这棵树的高度。

一共 logn 层

则要得到 次大值  ， 从最底层 ，a5 = 负无穷  ，按照原先 a5 上升的路再走一遍 ，每次上升一层，到顶层

即为次最大值

比较  logn -1 次