一道阿里電話面試中的算法題
文章分類: Java編程
電話面試算法題一道：找出數組中重復次數最多的元素并打印
問題不難，看你能給出更優的方案
- import java.util.HashMap;
- import java.util.Iterator;
- import java.util.Map.Entry;
- import commons.algorithm.sort.QuickSort;
- /**
- *找出數組中重復次數最多的元素并打印
- *
- */
- public class Problem_3{
- //先快速排序后循環查找O(n*log2(n)+n)
- public static void find1( int []arr){
- QuickSort.sort(arr);
- int max=arr[ 0 ];
- int pre= 1 ;
- int now= 1 ;
- for ( int i= 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)
- public static void find2( int []arr){
- int pre= 0 ;
- int max=arr[ 0 ];
- for ( int i= 0 ;i<arr.length;i++){
- int now= 0 ;
- for ( int j= 0 ;j<arr.length;j++){
- if (arr[i]==arr[j]){
- now++;
- }
- }
- if (now>=pre){
- max=arr[i];
- pre=now;
- }
- }
- }
- //通過Hash方式
- public static void find3( int []arr){
- HashMap<Integer,Integer>hm= new HashMap<Integer,Integer>();
- for ( int i= 0 ;i<arr.length;i++){
- if (hm.containsKey(arr[i])){
- int count=hm.get(arr[i]);
- hm.put(arr[i],++count);
- } else {
- hm.put(arr[i], 1 );
- }
- }
- Iterator<Entry<Integer,Integer>>it=hm.entrySet().iterator();
- int pre= 0 ;
- int max=arr[ 0 ];
- while (it.hasNext()){
- Entry<Integer,Integer>en=it.next();
- int key=en.getKey();
- int val=en.getValue();
- if (val>pre){
- pre=val;
- max=key;
- }
- }
- }
- public static void main(Stringargs[]){
- //數據量800重復元素多，查找時候分別是：463680195
- int arr2[]={ 0 , 1 , 2 ,.....
- , 0 , 1 , 2 , 3 , 6 , 7 , 8 , 9 };
- //數據量800重復元素少，查找時間分別是823727360
- int arr[]={ 0 , 0 , 0 , 11 , 12 , 13 , 14 , 5 , 6 ......
- , 51 , 52 , 53 ,, 728 , 29 , 730 , 731 , 3 , 794 , 95 , 796 , 797 , 798 , 799 };
- long start,end;
- start=System.currentTimeMillis();
- for ( int i= 0 ;i< 1000 ;i++)find1(arr);
- end=System.currentTimeMillis();
- System.out.println(end-start);
- start=System.currentTimeMillis();
- for ( int i= 0 ;i< 1000 ;i++)find2(arr);
- end=System.currentTimeMillis();
- System.out.println(end-start);
- start=System.currentTimeMillis();
- for ( int i= 0 ;i< 1000 ;i++)find3(arr);
- end=System.currentTimeMillis();
- System.out.println(end-start);
- }
- }
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
