对于长度为n的整型数组A，随机生成其数组元素值，然后实现一个线性时间的算法，在该数组中查找其中项。

 

 

1 package org.xiu68.exp.exp3; 2  3 import java.util.ArrayList; 4 import java.util.List; 5 import java.util.Random; 6  7 public class Exp3_1 { 8  9     //对于长度为n的整型数组A，随机生成其数组元素值，然后实现一个线性时间的算法，在该数组中查找其中项10     public static void main(String[] args) {11         // TODO Auto-generated method stub12         ArrayList
      
        array=new ArrayList<>();13         for(int j=0;j<10;j++){14             array.clear();15             for(int i=0;i<10;i++){16                 int k=new Random().nextInt(100);17                 array.add(k);18                 System.out.print(k+"  ");19             }20             System.out.println();21             System.out.println("中位数为"+findMedian(array,array.size()/2));22         }23     }24     25     //获取中位数26     public static int findMedian(List
       
         array,int k){27         28         int v=array.get(0);29         ArrayList
        
          leftList=new ArrayList<>();        //比v小的集合30         ArrayList
         
           equalList=new ArrayList<>();        //与v相等的集合31         ArrayList
          
            rightList=new ArrayList<>();        //比v大的集合32         33         for(int i=0;i
           
            v){36 rightList.add(value);37 }else if(value
            
             leftList.size() && k<=leftList.size()+equalList.size())48 return equalList.get(0);49 //findMedian(S,k)=findMedian(SR,k-|SL|-|SV|) 如果k>|SL|+|SV|50 else51 return findMedian(rightList,k-leftList.size()-equalList.size());52 }53 54 }