对于长度为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 ArrayListarray=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 }