如何加快這段java代碼？

如果該方法出現的次數超過數組大小的一半，則返回正整數數組中的數字，否則返回-1。我需要改善其更大陣列的運行時間(10^5<size<10^8)。有什麼建議麼？如何加快這段java代碼？

public static int findResult(int arr[],int len){ 

    int val=0; 
    HashMap<Integer,Integer> map=new HashMap<Integer,Integer>(); 
    for(int i=0;i<len;i++){ 
     if(map.containsKey(arr[i])){ 
      val = (Integer)map.get(arr[i]); 
      map.put(arr[i], val+1); 
     }else{ 
      val=1; 
      map.put(arr[i], val); 
     } 
    } 
    Iterator<Integer> it=map.keySet().iterator(); 
    while(it.hasNext()){ 
     int next=it.next(); 
     if((Integer)map.get(next)>(len/2)){ 
      return next; 
     } 
    } 
    return -1; 
}

來源

2013-05-05 Nishant

這可能應該發佈到[codereview]（h ttp：//codereview.stackexchange.com/），不是。 – 2013-05-05 12:20:34

此外，您的代碼在O（n）時間運行。這並不是很慢。 – supersam654 2013-05-05 12:22:48

（i）而不是containsKey + get，只需使用一個'get'並與'null'比較（ii）跟蹤第一個循環中的最高數字並擺脫第二個循環（iii）調整地圖的大小以開始並避免許多重新哈希操作 – assylias 2013-05-05 12:23:10

你可以做到這一點沒有地圖，消除對裝箱/拆箱，需要更換：

public static int findResult(int[] arr, int len) { 
    if(len == 0) return -1; 
    if(len == 1) return arr[0]; 

    int element = arr[0]; 
    int count = 1; 
    for(int i = 1; i < len; i++) { 
     if(arr[i] == element) { 
      count++; 
     } else if(count > 0) { 
      count--; 
     } else { 
      element = arr[i]; 
      count = 1; 
     } 
    } 

    count = 0; 
    for(int a:arr) { 
     if(a == element) { 
      count++; 
     } 
    } 

    return (count > len/2) ? element : -1; 
}

來源

2013-05-05 12:44:16 fgb

如果一個項目是大多數，這個算法是否僅僅工作？ – assylias 2013-05-05 13:09:11

@assylias如果沒有項目是多數，那麼最終的計數將是<= len/2，應該返回-1。 – fgb 2013-05-05 13:18:21

我錯過了第二個循環。下面是對算法的一個很好的解釋：http://stackoverflow.com/a/3740548/829571 – assylias 2013-05-05 13:38:03

爲什麼在每次迭代輸入哈希映射後，您不會比較長度（您正在運行的第二個迭代器循環）？到hashmap完成的時候，你知道結果，而且你只需要做一次。

來源

2013-05-05 12:25:45

這IMO更短，更有效的

public static int findResult(int arr[], int len) { 
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); 
    for (int i = 0; i < len; i++) { 
     Integer val = map.get(arr[i]); 
     if (val != null) { 
      map.put(arr[i], val + 1); 
     } else { 
      map.put(arr[i], 1); 
     } 
    } 
    for (Entry<Integer, Integer> e : map.entrySet()) { 
     if (e.getKey() > (len/2)) { 
      return e.getValue(); 
     } 
    } 
    return -1; 
}

1）原始版本使用2方法調用地圖

if(map.containsKey(arr[i])){ 
     val = (Integer)map.get(arr[i]);

礦採用一個map.get

2）本

while(it.hasNext()){ 
     int next=it.next(); 
     if((Integer)map.get(next)>(len/2)){

如此糟糕的表現明智，即使聲納或FindBugs的將iimediately檢測到它，並建議與我提供

來源

2013-05-05 12:28:22

雖然這仍然是O（n），但是這個輸入的大小可以在迭代一次和兩次之間產生差異。另外改變map.contains到你的get也是一樣的O（1）。 – 2013-05-05 12:33:28

每次增加某個變量的計數器時，可以使用一個臨時變量來存儲總是最大的數值，，檢查它是否大於臨時值，如果是，則替換它，否則繼續，這樣就可以不用第二個循環，你只是知道你的答案是在臨時變量

來源

2013-05-05 12:53:53 Dima

如何加快這段java代碼？

回答

相關問題