2

文字列の配列を指定して、特定の文字の出現頻度を見つけます。

例えば。配列 {"hon","bhig","zzz","hello"} と文字 'h' を指定すると、出力は 3 になります。

解決方法は次のとおりです。 アプローチ 1: 配列内のすべての文字列を反復処理し、現在の文字列にその文字が出現するたびにカウンターをインクリメントします。実行時間は O(n) です。ここで、n は配列内のすべての文字列の累積の長さです。

アプローチ 2: これは HashMap を使用して最適化できます。これは、文字列が配列内で繰り返される場合に特に役立ちます。これが私がやったことです: キー = 文字列と値 = その文字列が配列内で発生する回数である HashMap を取ります。指定された配列内のすべての文字列を、そのカウントとともに 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;
}
4

6 に答える 6

2

アプローチ 2 はあまり最適化されていません。実際にすべきことは、Map<Character,Integer>カウントする 2 番目のループを作成せず、各文字列の各文字をループする必要があることです。

アプローチ 1 は、実装によっては、文字列に出現する各文字のみをカウントしますが、文字が 2 回出現するかどうかを考慮し"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));
 }

どちらの方法でも、HashMap のドキュメントから、両方のアプローチが O(n) になります。

この実装は、基本操作 (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と同じように高速です）。これにより、速度が多少向上する可能性がありますが、必ずしもコードが「より良い」ものになるとは限りません。文字列内の char 検索の例は、このSO answer にあります。

于 2013-10-16T21:36:28.757 に答える