查找字符串數組中字符的頻率

給定一個字符串數組，找出特定字符出現的頻率。查找字符串數組中字符的頻率

例如。給定數組{「hon」，「bhig」，「zzz」，「hello」}和字符'h'，輸出爲3.

以下是我如何解決它：方法1：遍歷數組，每當該字符出現在當前字符串中時遞增計數器。運行時間是O（n），其中n是數組中所有字符串的累積長度。

方法2：這可以使用HashMap進行優化;如果字符串在數組中重複，這特別有用。以下是我所做的：使用HashMap，其中key = string，value =數組中出現字符串的次數。將給定數組中的所有字符串連同其計數一起放入HashMap中。然後迭代HashMap中的每個鍵值對，計算給定字符出現在鍵（字符串）中的次數，並將其增加HashMap中相應的值。

我的問題是：有沒有更好的方法來做到這一點？

下面的代碼：

注意：請閱讀全文，接受的答案。

public static int findFreq(String[] arr,char c) { 
    Map<String,Integer> map = new HashMap<String,Integer>(); 
    for(int i=0;i<arr.length;i++) { 
     if(map.containsKey(arr[i])) 
      map.put(arr[i],map.get(arr[i])+1); 
     else 
      map.put(arr[i], 1); 
    } 
    int freq=0; 
    for(Entry<String,Integer> entr:map.entrySet()) { 
     String s = entr.getKey(); 
     for(int i=0;i<s.length();i++) { 
      if(s.charAt(i)==c) 
       freq += entr.getValue(); 
     } 
    } 
    return freq; 
}

來源

2013-10-16 codewarrior

看到，因爲你將不得不看每個人字符數組來解決這個問題，你永遠不會比O（N）做的更好。我沒有看到如何通過字符串來繪製地圖是有幫助的（事實上，如果你再也不會看到'arr'，那麼你不需要地圖）。如果你想保留它，我會從字母表中的每個字母映射到它出現的次數（即'h - > 3'）。 –

計算字符串的哈希碼需要查看每個字母。當然，哈希碼可能已經被計算過一次（因此被緩存），第二種方法可能會有更多的工作，並且（平均而言）不能少工作。只有在字符串數量顯着多於1的情況下才有節省。 –

方法2並不是非常優化，你真正應該做的是創建一個Map<Character,Integer>然後你不需要第二個循環來計數，但是你需要循環每個字符串中的每個字符。

方法1，根據您的實現也只計算字符串中出現的每個字符，它是否考慮如果字符出現兩次，例如"hash"？

兩種方法都需要比較在EACH角色中的每個字符串再算上

這是方法2應該如何

public static int findFreq(String[] arr,char c) { 
    Map<Character,Integer> map = new HashMap<Character,Integer>(); 
    for(int i=0;i<arr.length;i++) { 
     for(Character ch : arr[i].toCharArray()){ 
      if(map.containsKey(ch)) 
       map.put(ch,map.get(ch)+1); 
      else 
       map.put(ch, 1); 
     } 
    } 
    return map.get(Character.valueOf(c)); 
}

無論哪種方式，這兩種方法將是爲O（n）， from docs for HashMap

此實現提供了恆定時間性能基本操作（獲取和放入）

但即使採用我上面提供的方法，在填充地圖時還需要額外的get。

所以方法1是更好，如果使用單個搜索，如果用反覆則接近2要走的路（但填充的方法外地圖）

一些指標可供您：

Number of Words | Array (approach 1) | Map (My approach 2) | Map (your approach 2) 
       |  (time in ms)  |  (time in ms)  |  (time in ms) 
       |  (groovy)/(java)  |  (groovy)/(java) |  (groovy)/(java)  
------------------------------------------------------------------------------------------- 
     43303  |   118/5  |   229/34  |   /16  
    417221  |   852/10  |  1088/120  |   /49 
    2086705  |  2929/45  |  5064/731  |   /219

我收回我的方法，看起來你的Map方法更快！

這是我的陣列方法（如果你的不同）

private static int findFreqArray(String[] arr, char c){ 
    int count = 0; 
    for(int i=0;i<arr.length;i++) { 
     for(char ch : arr[i].toCharArray()){ 
      if(ch == c) 
       count++; 
     } 
    } 
    return count; 
}

來源

2013-10-16 21:42:45

非常感謝你的指標，這真的解決了我的一些疑問。是的，許多人認爲，方法1似乎是最快的。 – codewarrior

是啊，看起來是爲什麼，我驚訝地發現你的地圖方法用2個循環更快，但現在我看它，在我的方法中調用'arr [i] .toCharArray（）'可能會減慢它的速度 –

也許更像是它映射每個字符，而數組方法（和你的地圖）只在字符匹配時映射。 –