2

Given an array of Strings, find the frequency of occurrence of a particular character.

eg. Given array {"hon","bhig","zzz","hello"} and character 'h', the output is 3.

Here's how I solved it: Approach 1: Iterate through every string in the array, increment a counter every time that character occurs in the current String. Run time is O(n), where n is the cumulative length of all strings in the array.

Approach 2: This can be optimized using a HashMap; this is particularly helpful if the strings are repeated in the array. Here's what I did: take a HashMap where key = string and value = number of times that string occurs in the array. Put all strings in the given array into the HashMap along with their counts. Then iterate over each key-value pair in the HashMap, count the number of times the given character appears in the key(string) and increment it by its corresponding value in the HashMap.

My question is: Is there a better way to do this?

Here's the code:

NOTE: PLEASE READ THE ENTIRE ACCEPTED ANSWER.

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;
}
4

6 回答 6

3

抱歉，我认为方法 2 会减慢速度。为了将每个字符串添加到 中HashMap，该方法计算哈希码，它查看字符串中的每个字符。因此，设置HashMap已经查看了每个字符串中的每个字符，这与您对方法 1 所做的事情一样长，而且您必须再次通过地图。

于 2013-10-16T21:37:55.663 回答
2

方法 1 在这里更可取。O(N)在最坏的情况下，成本是他们中的任何一个。用于记住旧访问字符串的第二种方法HashMap<String>（具有固有的散列成本）不会带来值得一提的性能改进。我们应该避免过早的优化，因为approach 1更简单。

于 2013-10-16T21:37:16.933 回答
2

方法2不是很优化，你真正应该做的是创建一个Map<Character,Integer>然后你不计算第二个循环，但你需要循环每个字符串中的每个字符。

方法 1，根据您的实现，也只计算字符串中出现的每个字符，是否考虑字符是否出现两次，例如"hash"？

任何一种方法都需要比较每个字符串中的每个字符，然后计数

这就是方法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)，来自HashMap 的文档

此实现为基本操作（get 和 put）提供恒定时间性能

但这就是说，即使使用我上面提供的方法，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-16T21:42:45.250 回答
1

不必要。另一种可能性是将您的数组“展平”为单个字符串并在其中搜索单个字符（与您的变体 1 一样快）。这可能会稍微加快速度，但不一定会使代码“更好”。可以在此SO answer中找到字符串中的字符搜索示例。

于 2013-10-16T21:36:28.757 回答
1

不，仅一次搜索就永远不会比 O(n) 做得更好。但是，如果您要针对同一个数组多次搜索不同的字符，您可以从遍历数组开始并构建一个从每个字符到其出现次数的哈希映射。然后，对于每次搜索，您只需要进行简单的常数时间查找，而不是 O(n) 搜索。

于 2013-10-16T21:43:50.520 回答
1

Hashmap 比第一个更慢。两种算法都需要从每个字符传递一次，因此都需要 O(n) 时间。但第一个更简单，执行的代码行更少。

不错的尝试:)

于 2013-10-16T21:45:26.820 回答