一道阿里电话面试中的算法题

电话面试算法题一道：找出数组中重复次数最多的元素并打印

 

问题不难，看你能给出更优的方案

 

 

importjava.util.HashMap;
importjava.util.Iterator;
importjava.util.Map.Entry;

importcommons.algorithm.sort.QuickSort;

/**
*找出数组中重复次数最多的元素并打印
*
*/
publicclassProblem_3{

//先快速排序后循环查找O(n*log2(n)+n)
publicstaticvoidfind1(int[]arr){

QuickSort.sort(arr);


intmax=arr[0];
intpre=1;
intnow=1;

for(inti=0;i<(arr.length-1);i++){

if(arr[i]==arr[i+1])
now++;
else{
if(now>=pre){
pre=now;
now=1;
max=arr[i];
}
}
}



}

//嵌套循环查找O(n*n)
publicstaticvoidfind2(int[]arr){


intpre=0;
intmax=arr[0];

for(inti=0;i<arr.length;i++){
intnow=0;
for(intj=0;j<arr.length;j++){

if(arr[i]==arr[j]){
now++;
}
}

if(now>=pre){
max=arr[i];
pre=now;
}


}



}

//通过Hash方式
publicstaticvoidfind3(int[]arr){
HashMap<Integer,Integer>hm=newHashMap<Integer,Integer>();
for(inti=0;i<arr.length;i++){
if(hm.containsKey(arr[i])){
intcount=hm.get(arr[i]);
hm.put(arr[i],++count);

}else{
hm.put(arr[i],1);
}
}

Iterator<Entry<Integer,Integer>>it=hm.entrySet().iterator();
intpre=0;
intmax=arr[0];
while(it.hasNext()){
Entry<Integer,Integer>en=it.next();
intkey=en.getKey();
intval=en.getValue();
if(val>pre){
pre=val;
max=key;
}

}



}
publicstaticvoidmain(Stringargs[]){

//数据量800重复元素多，查找时候分别是：463680195
intarr2[]={0,1,2,.....
,0,1,2,3,6,7,8,9};

//数据量800重复元素少，查找时间分别是823727360
intarr[]={0,0,0,11,12,13,14,5,6......
,51,52,53,,728,29,730,731,3,794,95,796,797,798,799};



longstart,end;

start=System.currentTimeMillis();
for(inti=0;i<1000;i++)find1(arr);
end=System.currentTimeMillis();
System.out.println(end-start);

start=System.currentTimeMillis();
for(inti=0;i<1000;i++)find2(arr);
end=System.currentTimeMillis();
System.out.println(end-start);


start=System.currentTimeMillis();
for(inti=0;i<1000;i++)find3(arr);
end=System.currentTimeMillis();
System.out.println(end-start);

}
}