分治与递归——找出数组中重复最多的元素算

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

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(String args[]){  

 

        //数据量800 重复元素多，查找时候分别是：   46   3680   195  

        int arr2[]={0,1,2,         .....         

                 ,0,1,2,3,6,7,8,9};  

          

        //数据量800 重复元素少，查找时间分别是      82   3727   360  

        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);  

          

     }